Submission #3132059


Source Code Expand

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

void add(int i, int x){
	while(i<=m){
		bit[i] += x;
		i += i&-i;
	}
}
int main(){
	int z,ans = 0;
	cin >> n >> q;
	int i;
	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]);
		}
	}
	m = v.size()+1;
	v.push_back(0);
	sort(v.begin(),v.end());
	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++;
	int 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];
		}
	}
	for(i=1;i<now;i++){
		//cout << i << " " << sum(i) << endl;
	}
	for(i=0;i<now;i++){
		//cout << i << " " << inv[i] << endl;
	}
	for(i=0;i<now;i++){
		//cout << i << " " << sum(i) << endl;
	}
	ans += a[0]+a[2*n-1];
	for(i=0;i<q;i++){
		if(p[i]==0 || p[i]==2*n-1){
			//cout << ans << endl;
			ans -= a[p[i]];
			ans += x[i];
			//cout << p[i] << " " << a[p[i]] << " " << x[i] << endl;
			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]);
			//cout << a[p[i]] << " " << b[p[i]] << " " << x[i] << " " << y[i] << " " << ans <<" " << cnt<< endl;
			for(int j=0;j<now;j++){
				//cout << j << " " << sum(j) << endl;
			}
			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];
		}
		//cout << ans << " " << cnt << endl;
		if(cnt%2==0){
			cout << ans << endl;
		}else{
			long long l=0,r=now,mid;
			int s = sum(z);
			//cout << i << " "  << p[i] << " " << x[i] << " " << y[i] << endl;
			//cout << l << " " << r << " " << z << endl;
			//cout << s << endl;
			while(r - l>1){
				//cout << l << " " << r << " " << endl;
				mid = (l+r)/2;
				if(sum(mid)>=s+1){
					r = mid;
				}else{
					l = mid;
				}
			}
			//cout << r << endl;
			long long m1 = inv[r];
			l=0,r=now;
			while(r - l>1){
				//cout << l << " " << r << endl;
				mid = (l+r)/2;
				if(sum(mid)<s){
					l = mid;
				}else{
					r = mid;
				}
			}
			//cout << r << endl;
			long long m2 = inv[r];
			//cout << m1 << " " << m2 << " " << endl;
			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 0
Code Size 2876 Byte
Status WA
Exec Time 748 ms
Memory 30956 KB

Judge Result

Set Name Sample Subtask1 Subtask2 All
Score / Max Score 0 / 0 0 / 200 0 / 300 0 / 200
Status
AC × 2
AC × 9
WA × 5
WA × 15
AC × 12
WA × 31
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 WA 2 ms 6400 KB
s1_07.txt WA 2 ms 6400 KB
s1_08.txt WA 2 ms 6400 KB
s1_09.txt WA 2 ms 6400 KB
s1_10.txt WA 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 WA 11 ms 7040 KB
s2_15.txt WA 12 ms 7168 KB
s2_16.txt WA 188 ms 18032 KB
s2_17.txt WA 152 ms 16372 KB
s2_18.txt WA 284 ms 22128 KB
s2_19.txt WA 284 ms 22128 KB
s2_20.txt WA 285 ms 22128 KB
s2_21.txt WA 285 ms 22128 KB
s2_22.txt WA 11 ms 7040 KB
s2_23.txt WA 12 ms 7168 KB
s2_24.txt WA 11 ms 7040 KB
s2_25.txt WA 343 ms 24048 KB
s2_26.txt WA 343 ms 24048 KB
s2_27.txt WA 352 ms 24048 KB
s2_28.txt WA 342 ms 24048 KB
s3_29.txt WA 248 ms 17780 KB
s3_30.txt WA 341 ms 17780 KB
s3_31.txt WA 235 ms 19696 KB
s3_32.txt WA 623 ms 26224 KB
s3_33.txt WA 251 ms 17780 KB
s3_34.txt WA 748 ms 29676 KB
s3_35.txt WA 735 ms 30956 KB
s3_36.txt WA 693 ms 27760 KB
s3_37.txt WA 702 ms 27760 KB
s3_38.txt WA 722 ms 27760 KB
s3_39.txt WA 703 ms 27760 KB
s3_40.txt AC 237 ms 7168 KB
s3_41.txt AC 235 ms 7168 KB