Submission #3132079


Source Code Expand

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

#define ll long long
using namespace std;
ll bit[400010],a[200010],b[200010],p[100010],x[100010],y[100010],n,q,inv[300010],m;
vector<ll> v;
map<ll,ll> mp;
ll sum(ll i){
	ll s = 0;
	while(i>0){
		s += bit[i];
		i -= i&-i;
	}
	return s;
}

void add(ll i, ll x){
	while(i<=m){
		bit[i] += x;
		i += i&-i;
	}
}
int main(){
	ll z,ans=0,i;
	cin >> n >> q;
	for(i=0;i<2*n;i++){
		cin >> a[i];
	}
	for(i=0;i<2*n;i++){
		cin >> b[i];
	}
	for(i=1;i<2*n-1;i++){
		v.push_back(a[i]-b[i]);
	}
	for(i=0;i<q;i++){
		cin >> p[i] ;
		p[i]--;
		cin>> x[i] >> y[i];
		if(p[i]!=0 && p[i]!=2*n-1){
			v.push_back(x[i]-y[i]);
		}
	}
	v.push_back(0);
	sort(v.begin(),v.end());
	m = v.size()+1;
	int now = 1;
	mp[v[0]] = 1;
	inv[1] = v[0];
	if(v[0]==0){
		z = 1;
	}
	for(i=1;i<v.size();i++){
		if(v[i]>v[i-1]){
			now++;
		}
		mp[v[i]] = now;
		inv[now] = v[i];
		if(v[i]==0){
			z = now;
		}
	}
	now++;
	ll cnt = 0;
	for(i=1;i<2*n-1;i++){
		add(mp[a[i]-b[i]],1);
		if(a[i]>=b[i]){
			ans += a[i];
			cnt += 1;
		}else{
			ans += b[i];
		}
	}
	ans += a[0]+a[2*n-1];
	for(i=0;i<q;i++){
		if(p[i]==0 || p[i]==2*n-1){
			ans -= a[p[i]];
			ans += x[i];
			a[p[i]] = x[i];
			b[p[i]] = y[i];
		}else{
			ans -= max(a[p[i]],b[p[i]]);
			ans += max(x[i],y[i]);
			add(mp[a[p[i]] - b[p[i]]],-1);
			add(mp[x[i] - y[i]],1);
			if(a[p[i]]-b[p[i]]>0 ^ x[i]-y[i]>0){
				cnt++;
			}
			a[p[i]] = x[i];
			b[p[i]] = y[i];
		}
		if(cnt%2==0){
			cout << ans << endl;
		}else{
			long long l=0,r=now,mid;
			int s = sum(z);
			while(r - l>1){
				mid = (l+r)/2;
				if(sum(mid)>=s+1){
					r = mid;
				}else{
					l = mid;
				}
			}
			long long m1 = inv[r];
			l=0,r=now;
			while(r - l>1){
				mid = (l+r)/2;
				if(sum(mid)<s){
					l = mid;
				}else{
					r = mid;
				}
			}
			long long m2 = inv[r];
			cout << max(ans - m1,ans + m2) << endl;
		}
	}
}

Submission Info

Submission Time
Task C - Paired Parentheses
User Alt3
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2019 Byte
Status AC
Exec Time 738 ms
Memory 31084 KB

Judge Result

Set Name Sample Subtask1 Subtask2 All
Score / Max Score 0 / 0 200 / 200 300 / 300 200 / 200
Status
AC × 2
AC × 14
AC × 15
AC × 43
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 2 ms 6400 KB
00_example_02.txt AC 2 ms 6400 KB
s1_01.txt AC 2 ms 6400 KB
s1_02.txt AC 2 ms 6400 KB
s1_03.txt AC 2 ms 6400 KB
s1_04.txt AC 2 ms 6400 KB
s1_05.txt AC 2 ms 6400 KB
s1_06.txt AC 2 ms 6400 KB
s1_07.txt AC 2 ms 6400 KB
s1_08.txt AC 2 ms 6400 KB
s1_09.txt AC 2 ms 6400 KB
s1_10.txt AC 2 ms 6400 KB
s1_11.txt AC 2 ms 6400 KB
s1_12.txt AC 2 ms 6400 KB
s1_13.txt AC 2 ms 6400 KB
s2_14.txt AC 11 ms 7040 KB
s2_15.txt AC 12 ms 7168 KB
s2_16.txt AC 186 ms 18032 KB
s2_17.txt AC 152 ms 16372 KB
s2_18.txt AC 288 ms 22128 KB
s2_19.txt AC 285 ms 22128 KB
s2_20.txt AC 282 ms 22128 KB
s2_21.txt AC 292 ms 22128 KB
s2_22.txt AC 11 ms 7040 KB
s2_23.txt AC 12 ms 7168 KB
s2_24.txt AC 12 ms 7040 KB
s2_25.txt AC 350 ms 24176 KB
s2_26.txt AC 344 ms 24048 KB
s2_27.txt AC 346 ms 24048 KB
s2_28.txt AC 339 ms 24048 KB
s3_29.txt AC 243 ms 17908 KB
s3_30.txt AC 336 ms 17908 KB
s3_31.txt AC 233 ms 19696 KB
s3_32.txt AC 616 ms 26480 KB
s3_33.txt AC 248 ms 17908 KB
s3_34.txt AC 729 ms 30572 KB
s3_35.txt AC 738 ms 31084 KB
s3_36.txt AC 684 ms 28144 KB
s3_37.txt AC 698 ms 28144 KB
s3_38.txt AC 683 ms 28144 KB
s3_39.txt AC 686 ms 28144 KB
s3_40.txt AC 231 ms 7168 KB
s3_41.txt AC 232 ms 7168 KB