Submission #1870987
Source Code Expand
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <set> using namespace std; #define MAXN 100000 #define ll long long #define INFLL 0x3f3f3f3f3f3f3f3fll #define rint register int #define gc() getchar() inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc()) { for(; ch < '0' || ch > '9'; sgn = ch, ch = gc()); for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc()); return sgn-'-'?ans:-ans; } #define BUF_SIZE 1000000 #define _END fwrite(_Ob,1,_O-_Ob,stdout), _O = _Ob #define Outc(a) (*_O++ = a) char _Ob[BUF_SIZE+5], *_O = _Ob, _Os[25], *_Ot; template <typename T> inline void Out(T x) { if(!x){Outc('0'); return;} if(x < 0) Outc('-'), x = -x; for(_Ot = _Os; x; *_Ot++ = x%10+'0', x /= 10); for(; _Ot != _Os; Outc(*--_Ot)); if(_O-_Ob >= BUF_SIZE-50) _END; } int n, q, a[MAXN+5], b[MAXN+5]; multiset<int> Pos, Neg; multiset<int>::iterator it; ll base, sum; int main() { n = read()<<1, q = read(); for(rint i = 1; i <= n; base += (a[i++]=read())); for(rint i = 1; i <= n; b[i++] = read()); for(rint i = 2; i < n; b[i]>=a[i] ? sum += b[i]-a[i], Pos.insert(b[i]-a[i]) : Neg.insert(b[i]-a[i]), i++); for(rint p; q--; Out(base+(Pos.size()&1?max(sum+(Neg.size()?*--Neg.end():INFLL),sum-*Pos.begin()):sum)), Outc('\n')) { p = read(), base -= a[p], p>1&&p<n ? it = (b[p]>=a[p] ? sum -= b[p]-a[p], Pos.find(b[p]-a[p]) : Neg.find(b[p]-a[p])), (b[p]>=a[p]?Pos:Neg).erase(it),0 : 0; a[p] = read(), b[p] = read(), base += a[p], p>1&&p<n ? b[p]>=a[p] ? sum += b[p]-a[p], Pos.insert(b[p]-a[p]) : Neg.insert(b[p]-a[p]),0 : 0; } _END; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Paired Parentheses |
User | Magolor |
Language | C++14 (GCC 5.4.1) |
Score | 200 |
Code Size | 1649 Byte |
Status | RE |
Exec Time | 2103 ms |
Memory | 4992 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 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 | 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 | 4 ms | 768 KB |
s2_15.txt | AC | 4 ms | 768 KB |
s2_16.txt | TLE | 2103 ms | 1280 KB |
s2_17.txt | RE | 103 ms | 640 KB |
s2_18.txt | RE | 103 ms | 640 KB |
s2_19.txt | RE | 117 ms | 1664 KB |
s2_20.txt | RE | 103 ms | 640 KB |
s2_21.txt | RE | 102 ms | 640 KB |
s2_22.txt | AC | 4 ms | 768 KB |
s2_23.txt | AC | 4 ms | 768 KB |
s2_24.txt | AC | 4 ms | 768 KB |
s2_25.txt | RE | 126 ms | 1664 KB |
s2_26.txt | RE | 104 ms | 640 KB |
s2_27.txt | RE | 105 ms | 640 KB |
s2_28.txt | RE | 105 ms | 640 KB |
s3_29.txt | TLE | 2103 ms | 1408 KB |
s3_30.txt | AC | 80 ms | 4992 KB |
s3_31.txt | RE | 103 ms | 640 KB |
s3_32.txt | RE | 117 ms | 3200 KB |
s3_33.txt | RE | 102 ms | 640 KB |
s3_34.txt | RE | 102 ms | 640 KB |
s3_35.txt | RE | 117 ms | 1664 KB |
s3_36.txt | RE | 126 ms | 1664 KB |
s3_37.txt | RE | 105 ms | 640 KB |
s3_38.txt | RE | 106 ms | 640 KB |
s3_39.txt | RE | 106 ms | 640 KB |
s3_40.txt | AC | 20 ms | 1792 KB |
s3_41.txt | AC | 20 ms | 1792 KB |