Submission #2559084
Source Code Expand
// 基本テンプレート #include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <cfloat> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <fstream> #include <functional> using namespace std; #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++) #define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++) #define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--) #define debug(...) fprintf(stderr, __VA_ARGS__) #define int long long int template<typename T> void chmax(T &a, T b) {a = max(a, b);} template<typename T> void chmin(T &a, T b) {a = min(a, b);} template<typename T> void chadd(T &a, T b) {a = a + b;} typedef pair<int, int> pii; typedef long long ll; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const ll INF = 1001001001001001LL; const ll MOD = 1000000007LL; int N, Q; signed main() { cin >> N >> Q; int L = 2*N; vector<int> A(L), B(L); for(int i=0; i<L; i++) cin >> A[i]; for(int i=0; i<L; i++) cin >> B[i]; int base = A[0] + A[L-1]; int asum = accumulate(A.begin(), A.end(), 0LL); set< pair<int, int> > S; // B - A >= 0 全部取った時の和 int cur_max = 0; for(int i=1; i<L-1; i++) { int diff = B[i] - A[i]; if(diff >= 0) { S.insert(make_pair(i, diff)); cur_max += diff; } } for(int i=0; i<Q; i++) { int p, x, y; cin >> p >> x >> y; p--; asum -= A[p]; if(p != 0 && p != L-1) { pair<int, int> elem = make_pair(p, B[p] - A[p]); if(S.count(elem)) { S.erase(elem); cur_max -= B[p] - A[p]; } } A[p] = x, B[p] = y; asum += A[p]; if(p != 0 && p != L-1) { pair<int, int> n_elem = make_pair(p, B[p] - A[p]); if(n_elem.second >= 0) { S.insert(n_elem); cur_max += n_elem.second; } } int sz = S.size(), tmp_max = cur_max; for(auto it=S.begin(); it!=S.end(); it++) { if(sz % 2 == 0) break; sz--; tmp_max -= it -> second; } // printf("asum = %lld, tmp_max = %lld\n", asum, tmp_max); cout << asum + tmp_max << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Paired Parentheses |
User | tsutaj |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2635 Byte |
Status | WA |
Exec Time | 510 ms |
Memory | 11136 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 200 | 0 / 300 | 0 / 200 | ||||||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt |
Subtask1 | 00_example_01.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt |
Subtask2 | s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt |
All | 00_example_01.txt, 00_example_02.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt, s3_29.txt, s3_30.txt, s3_31.txt, s3_32.txt, s3_33.txt, s3_34.txt, s3_35.txt, s3_36.txt, s3_37.txt, s3_38.txt, s3_39.txt, s3_40.txt, s3_41.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 1 ms | 256 KB |
00_example_02.txt | WA | 1 ms | 256 KB |
s1_01.txt | WA | 1 ms | 256 KB |
s1_02.txt | WA | 1 ms | 256 KB |
s1_03.txt | WA | 1 ms | 256 KB |
s1_04.txt | AC | 1 ms | 256 KB |
s1_05.txt | WA | 1 ms | 256 KB |
s1_06.txt | AC | 1 ms | 256 KB |
s1_07.txt | AC | 1 ms | 256 KB |
s1_08.txt | AC | 1 ms | 256 KB |
s1_09.txt | AC | 1 ms | 256 KB |
s1_10.txt | AC | 1 ms | 256 KB |
s1_11.txt | AC | 1 ms | 256 KB |
s1_12.txt | AC | 1 ms | 256 KB |
s1_13.txt | AC | 1 ms | 256 KB |
s2_14.txt | WA | 8 ms | 640 KB |
s2_15.txt | AC | 8 ms | 768 KB |
s2_16.txt | WA | 108 ms | 6656 KB |
s2_17.txt | AC | 88 ms | 5632 KB |
s2_18.txt | WA | 159 ms | 9600 KB |
s2_19.txt | WA | 161 ms | 9600 KB |
s2_20.txt | WA | 167 ms | 9600 KB |
s2_21.txt | AC | 160 ms | 9600 KB |
s2_22.txt | WA | 7 ms | 640 KB |
s2_23.txt | AC | 8 ms | 640 KB |
s2_24.txt | WA | 8 ms | 640 KB |
s2_25.txt | WA | 204 ms | 9600 KB |
s2_26.txt | WA | 204 ms | 9600 KB |
s2_27.txt | AC | 204 ms | 9600 KB |
s2_28.txt | WA | 207 ms | 9600 KB |
s3_29.txt | WA | 167 ms | 5504 KB |
s3_30.txt | WA | 256 ms | 3712 KB |
s3_31.txt | WA | 142 ms | 7808 KB |
s3_32.txt | WA | 427 ms | 8832 KB |
s3_33.txt | WA | 170 ms | 5504 KB |
s3_34.txt | WA | 488 ms | 11136 KB |
s3_35.txt | WA | 497 ms | 11136 KB |
s3_36.txt | WA | 505 ms | 11136 KB |
s3_37.txt | WA | 504 ms | 11136 KB |
s3_38.txt | WA | 505 ms | 11136 KB |
s3_39.txt | WA | 510 ms | 11136 KB |
s3_40.txt | AC | 239 ms | 1024 KB |
s3_41.txt | AC | 240 ms | 1024 KB |