Submission #2710058
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long lli; typedef double lld; typedef vector<lli> vll; typedef vector<bool> vbl; typedef vector<double> vdl; typedef vector<vector<lli>> mat; typedef vector<vdl> mad; typedef unordered_map<lli,unordered_map<lli,lli>> graph; typedef complex<double> cmp; typedef vector<cmp> vcl; lli n,q; vll a,b,c; multiset<lli> l,r; lli ans = 0; lli p,x,y; int main(){ cin >> n >> q; a = vll(2*n); b = vll(2*n); c = vll(2*n); for(lli i = 0;i < 2*n;i++) cin >> a[i]; for(lli i = 0;i < 2*n;i++) cin >> b[i]; for(lli i = 0;i < 2*n;i++) c[i] = a[i]-b[i]; ans = accumulate(a.begin(),a.end(),0ll); for(lli i = 1;i < 2*n-1;i++){ if(c[i] < 0){ r.insert(c[i]); }else{ l.insert(c[i]); } } for(lli x : r){ ans -= x; } for(lli i = 0;i < q;i++){ cin >> p >> x >> y; p--; if(p >= 1 && p < 2*n-1){ if(l.find(c[p]) != l.end()) l.erase(l.find(c[p])); else if(r.find(c[p]) != r.end()){ r.erase(r.find(c[p])); ans += c[p]; } } ans -= a[p]; a[p] = x; b[p] = y; c[p] = a[p]-b[p]; ans += a[p]; if(p >= 1 && p < 2*n-1){ if(c[p] < 0){ r.insert(c[p]); ans -= c[p]; } else l.insert(c[p]); } if(r.size()%2 == 1 && *r.rbegin()+*l.begin() < 0) cout << ans-*l.begin() << endl; else if(r.size()%2 == 1 && *r.rbegin()+*l.begin() >= 0) cout << ans+*r.rbegin() << endl; else cout << ans << endl; } }
Submission Info
Submission Time | |
---|---|
Task | C - Paired Parentheses |
User | deoxy |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1555 Byte |
Status | AC |
Exec Time | 590 ms |
Memory | 15744 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 300 / 300 | 200 / 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 | AC | 1 ms | 256 KB |
s1_01.txt | AC | 1 ms | 256 KB |
s1_02.txt | AC | 1 ms | 256 KB |
s1_03.txt | AC | 1 ms | 256 KB |
s1_04.txt | AC | 1 ms | 256 KB |
s1_05.txt | AC | 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 | AC | 9 ms | 896 KB |
s2_15.txt | AC | 9 ms | 896 KB |
s2_16.txt | AC | 130 ms | 9984 KB |
s2_17.txt | AC | 106 ms | 8320 KB |
s2_18.txt | AC | 193 ms | 14336 KB |
s2_19.txt | AC | 194 ms | 14336 KB |
s2_20.txt | AC | 194 ms | 14336 KB |
s2_21.txt | AC | 194 ms | 14336 KB |
s2_22.txt | AC | 8 ms | 896 KB |
s2_23.txt | AC | 9 ms | 896 KB |
s2_24.txt | AC | 9 ms | 896 KB |
s2_25.txt | AC | 236 ms | 14336 KB |
s2_26.txt | AC | 237 ms | 14336 KB |
s2_27.txt | AC | 238 ms | 14336 KB |
s2_28.txt | AC | 238 ms | 14336 KB |
s3_29.txt | AC | 200 ms | 7936 KB |
s3_30.txt | AC | 287 ms | 4992 KB |
s3_31.txt | AC | 165 ms | 11520 KB |
s3_32.txt | AC | 510 ms | 12416 KB |
s3_33.txt | AC | 200 ms | 7808 KB |
s3_34.txt | AC | 585 ms | 15744 KB |
s3_35.txt | AC | 590 ms | 15744 KB |
s3_36.txt | AC | 566 ms | 15744 KB |
s3_37.txt | AC | 559 ms | 15744 KB |
s3_38.txt | AC | 558 ms | 15744 KB |
s3_39.txt | AC | 573 ms | 15744 KB |
s3_40.txt | AC | 236 ms | 1024 KB |
s3_41.txt | AC | 237 ms | 1024 KB |