Submission #2069319
Source Code Expand
#include <iostream>
#define llint long long
#define inf 1000000000000000000
using namespace std;
llint N, Q;
llint a[200005], b[200005];
llint dif[200005];
llint pseg[1<<19];
void pinit()
{
for(int i = 0; i < (1<<19); i++) pseg[i] = inf;
}
void pupdate(llint k, llint val)
{
k += 1<<18;
pseg[k] = val;
while(k > 1){
k /= 2;
pseg[k] = min(pseg[2*k], pseg[2*k+1]);
}
}
llint pquery(llint a, llint b, llint k, llint l, llint r)
{
if(r < a || b < l) return inf;
if(a <= l && r <= b) return pseg[k];
llint lval = pquery(a, b, k*2, l, (l+r)/2);
llint rval = pquery(a, b, k*2+1, (l+r)/2+1, r);
return min(lval, rval);
}
llint nseg[1<<19];
void ninit()
{
for(int i = 0; i < (1<<19); i++) nseg[i] = -inf;
}
void nupdate(llint k, llint val)
{
k += 1<<18;
nseg[k] = val;
while(k > 1){
k /= 2;
nseg[k] = max(nseg[2*k], nseg[2*k+1]);
}
}
llint nquery(llint a, llint b, llint k, llint l, llint r)
{
if(r < a || b < l) return -inf;
if(a <= l && r <= b) return nseg[k];
llint lval = nquery(a, b, k*2, l, (l+r)/2);
llint rval = nquery(a, b, k*2+1, (l+r)/2+1, r);
return max(lval, rval);
}
int main(void)
{
pinit(), ninit();
cin >> N >> Q;
for(int i = 1; i <= 2*N; i++) cin >> a[i];
for(int i = 1; i <= 2*N; i++) cin >> b[i];
llint asum = 0;
for(int i = 1; i <= 2*N; i++){
asum += a[i];
dif[i] = b[i] - a[i];
}
llint pcnt = 0, psum = 0;
for(int i = 2; i <= 2*N-1; i++){
if(dif[i] >= 0){
pupdate(i, dif[i]);
pcnt++;
psum += dif[i];
}
else nupdate(i, dif[i]);
}
llint p, x, y;
for(int q = 0; q < Q; q++){
cin >> p >> x >> y;
if(p == 1 || p == 2*N){
asum = asum - a[p] + x;
a[p] = x;
goto end;
}
if(dif[p] >= 0 && y - x < 0) pcnt--;
if(dif[p] < 0 && y - x >= 0) pcnt++;
asum = asum - a[p] + x;
a[p] = x;
if(dif[p] >= 0){
pupdate(p, inf);
psum -= dif[p];
}
else nupdate(p, -inf);
dif[p] = y - x;
if(dif[p] >= 0){
pupdate(p, dif[p]);
psum += dif[p];
}
else nupdate(p, dif[p]);
end:;
llint ans;
if(pcnt % 2 == 0) ans = asum + psum;
else{
ans = max(asum + psum + nquery(2, 2*N-1, 1, 0, (1<<18)-1),
asum + psum - pquery(2, 2*N-1, 1, 0, (1<<18)-1));
}
cout << ans << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Paired Parentheses |
User |
leaf1415 |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2332 Byte |
Status |
AC |
Exec Time |
492 ms |
Memory |
14592 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 |
4 ms |
12544 KB |
00_example_02.txt |
AC |
4 ms |
12544 KB |
s1_01.txt |
AC |
4 ms |
12544 KB |
s1_02.txt |
AC |
4 ms |
12544 KB |
s1_03.txt |
AC |
4 ms |
12544 KB |
s1_04.txt |
AC |
4 ms |
12544 KB |
s1_05.txt |
AC |
4 ms |
12544 KB |
s1_06.txt |
AC |
4 ms |
12544 KB |
s1_07.txt |
AC |
4 ms |
12544 KB |
s1_08.txt |
AC |
4 ms |
12544 KB |
s1_09.txt |
AC |
6 ms |
12672 KB |
s1_10.txt |
AC |
4 ms |
12544 KB |
s1_11.txt |
AC |
4 ms |
12544 KB |
s1_12.txt |
AC |
4 ms |
12544 KB |
s1_13.txt |
AC |
4 ms |
12544 KB |
s2_14.txt |
AC |
9 ms |
12544 KB |
s2_15.txt |
AC |
10 ms |
12544 KB |
s2_16.txt |
AC |
91 ms |
12672 KB |
s2_17.txt |
AC |
76 ms |
12544 KB |
s2_18.txt |
AC |
132 ms |
13184 KB |
s2_19.txt |
AC |
130 ms |
13184 KB |
s2_20.txt |
AC |
130 ms |
13184 KB |
s2_21.txt |
AC |
130 ms |
13184 KB |
s2_22.txt |
AC |
10 ms |
12544 KB |
s2_23.txt |
AC |
10 ms |
12544 KB |
s2_24.txt |
AC |
10 ms |
12544 KB |
s2_25.txt |
AC |
175 ms |
13184 KB |
s2_26.txt |
AC |
175 ms |
13184 KB |
s2_27.txt |
AC |
175 ms |
13184 KB |
s2_28.txt |
AC |
176 ms |
13184 KB |
s3_29.txt |
AC |
149 ms |
12928 KB |
s3_30.txt |
AC |
243 ms |
13440 KB |
s3_31.txt |
AC |
115 ms |
12800 KB |
s3_32.txt |
AC |
381 ms |
14080 KB |
s3_33.txt |
AC |
152 ms |
12928 KB |
s3_34.txt |
AC |
430 ms |
14592 KB |
s3_35.txt |
AC |
435 ms |
14592 KB |
s3_36.txt |
AC |
492 ms |
14592 KB |
s3_37.txt |
AC |
480 ms |
14592 KB |
s3_38.txt |
AC |
483 ms |
14592 KB |
s3_39.txt |
AC |
478 ms |
14592 KB |
s3_40.txt |
AC |
248 ms |
13312 KB |
s3_41.txt |
AC |
245 ms |
13312 KB |