oj.uz

Submission #64226

# Submission time Handle Problem Language Result Execution time Memory
64226 2018-08-03T14:06:56 Z jangwonyoung Election (BOI18_election) C++14
100 / 100
 1434 ms 46344 KB 
#include<iostream>
#include<vector>
using namespace std;
const int N=5e5+1,X=1e6+1,TS=1<<20;
#define fi first
#define se second
#define pb push_back
int n,q;
int a[N];
int pre[N];
int nxt[N];
int v[X];
int sum[TS],mi[TS],cnt[TS];
int ans[N];
vector<pair<int,int> >qr[N];
void upd(int id,int l,int r,int pos,int v1,int v2){
	if(l==r){
		sum[id]+=v1;
		mi[id]=min(sum[id],0);
		cnt[id]+=v2;
		return;
	}
	int mid=(l+r)/2;
	if(pos<=mid) upd(id*2,l,mid,pos,v1,v2);
	else upd(id*2+1,mid+1,r,pos,v1,v2);
	sum[id]=sum[id*2]+sum[id*2+1];
	mi[id]=min(mi[id*2+1],mi[id*2]+sum[id*2+1]);
	cnt[id]=cnt[id*2]+cnt[id*2+1];
}
int qr1(int id,int l,int r,int ll,int rr){
	if(l>rr || r<ll) return 0;
	if(ll<=l && r<=rr) return cnt[id];
	int mid=(l+r)/2;
	return qr1(id*2,l,mid,ll,rr)+qr1(id*2+1,mid+1,r,ll,rr);
}
pair<int,int> qr2(int id,int l,int r,int ll,int rr){
	if(l>rr || r<ll) return {0,0};
	if(ll<=l && r<=rr) return {sum[id],mi[id]};
	int mid=(l+r)/2;
	pair<int,int>t1=qr2(id*2,l,mid,ll,rr),t2=qr2(id*2+1,mid+1,r,ll,rr);
	return {t1.fi+t2.fi,min(t2.se,t1.se+t2.fi)};
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for(int i=1; i<=n ;i++){
		char c;
		cin >> c;
		a[i]=(c=='C'?1:-1);
		pre[i]=pre[i-1]+a[i];
		if(v[pre[i]+n]==0 && pre[i]!=0){
			if(pre[i]<0) upd(1,1,n,i,0,1);
			else upd(1,1,n,i,a[i],0);
		}
		else{
			nxt[v[pre[i]+n]]=i;
			upd(1,1,n,i,a[i],0);
		}
		v[pre[i]+n]=i;
	}
	cin >> q;
	for(int i=1; i<=q ;i++){
		int l,r;
		cin >> l >> r;
		qr[l].pb({r,i});
	}
	for(int i=1; i<=n ;i++){
		for(auto cur:qr[i]){
			ans[cur.se]=qr1(1,1,n,i,cur.fi)-qr2(1,1,n,i,cur.fi).se;
		}
		if(a[i]==-1) upd(1,1,n,i,-1,-1);
		else if(nxt[i-1]!=0) upd(1,1,n,nxt[i-1],1,1);
	}
	for(int i=1; i<=q ;i++) cout << ans[i] << '\n';
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12284 KB Output is correct
2 Correct 19 ms 12392 KB Output is correct
3 Correct 18 ms 12392 KB Output is correct
4 Correct 17 ms 12400 KB Output is correct
5 Correct 15 ms 12408 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12284 KB Output is correct
2 Correct 19 ms 12392 KB Output is correct
3 Correct 18 ms 12392 KB Output is correct
4 Correct 17 ms 12400 KB Output is correct
5 Correct 15 ms 12408 KB Output is correct
6 Correct 176 ms 18268 KB Output is correct
7 Correct 167 ms 18268 KB Output is correct
8 Correct 158 ms 18268 KB Output is correct
9 Correct 144 ms 18268 KB Output is correct
10 Correct 137 ms 18312 KB Output is correct
11 Correct 163 ms 18428 KB Output is correct
12 Correct 172 ms 18428 KB Output is correct
13 Correct 166 ms 18436 KB Output is correct
14 Correct 142 ms 18552 KB Output is correct
15 Correct 141 ms 18552 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12284 KB Output is correct
2 Correct 19 ms 12392 KB Output is correct
3 Correct 18 ms 12392 KB Output is correct
4 Correct 17 ms 12400 KB Output is correct
5 Correct 15 ms 12408 KB Output is correct
6 Correct 176 ms 18268 KB Output is correct
7 Correct 167 ms 18268 KB Output is correct
8 Correct 158 ms 18268 KB Output is correct
9 Correct 144 ms 18268 KB Output is correct
10 Correct 137 ms 18312 KB Output is correct
11 Correct 163 ms 18428 KB Output is correct
12 Correct 172 ms 18428 KB Output is correct
13 Correct 166 ms 18436 KB Output is correct
14 Correct 142 ms 18552 KB Output is correct
15 Correct 141 ms 18552 KB Output is correct
16 Correct 1290 ms 44976 KB Output is correct
17 Correct 1132 ms 44976 KB Output is correct
18 Correct 1115 ms 44976 KB Output is correct
19 Correct 1170 ms 44976 KB Output is correct
20 Correct 1140 ms 44976 KB Output is correct
21 Correct 1212 ms 46344 KB Output is correct
22 Correct 1434 ms 46344 KB Output is correct
23 Correct 1322 ms 46344 KB Output is correct
24 Correct 1194 ms 46344 KB Output is correct
25 Correct 1084 ms 46344 KB Output is correct