oj.uz

Submission #535286

# Submission time Handle Problem Language Result Execution time Memory
535286 2022-03-09T22:38:22 Z new_acc Election (BOI18_election) C++14
100 / 100
 997 ms 51676 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e5+10;
const int SS=1<<19;
int lazy[SS*2+10],seg[SS*2+10],seg2[SS*2+10],naj[N];
int sp[N],ans[N];
vector<pair<int,int> >zap[N];
void push(int v){
	seg[v*2]+=lazy[v],seg[v*2+1]+=lazy[v];
	lazy[v*2]+=lazy[v],lazy[v*2+1]+=lazy[v];
	lazy[v]=0;
}
void upd(int pocz,int kon,int x,int p=0,int k=SS-1,int v=1){
	if(p>kon or k<pocz) return;
	if(p>=pocz and k<=kon){
		seg[v]+=x,lazy[v]+=x;
		return;
	}
	push(v);
	upd(pocz,kon,x,p,(p+k)>>1,(v<<1)),upd(pocz,kon,x,((p+k)>>1)+1,k,(v<<1)+1);
	seg[v]=min(seg[v<<1],seg[(v<<1)+1]);
}
int Query(int pocz,int kon,int p=0,int k=SS-1,int v=1){
	if(p>kon or k<pocz) return INT_MAX;
	if(p>=pocz and k<=kon) return seg[v];
	push(v);
	return min(Query(pocz,kon,p,(p+k)>>1,v<<1),Query(pocz,kon,((p+k)>>1)+1,k,(v<<1)+1));
}
void upd2(int a,int ind){
	for(ind+=SS;ind>0;ind>>=1) seg2[ind]+=a;
}
int Query2(int a,int b){
	int res=0;
	for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
		if(!(a&1)) res+=seg2[a+1];
		if(b&1) res+=seg2[b-1];
	}
	return res;
}
void single(int x){
	for(auto u:zap[x]){
		int pom=Query(x,u.fi)-Query(u.fi+1,u.fi+1);
		ans[u.se]=Query2(x,u.fi)+(pom>0?0:abs(pom));
	}
	if(sp[x]>sp[x-1]) if(naj[x]!=-1) upd2(1,naj[x]),upd(1,naj[x],1);
}
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		char a;
		cin>>a;
		if(a=='C') sp[i]=sp[i-1]+1;
		else sp[i]=sp[i-1]-1;
	}
	deque<pair<int,int> >deq;
	for(int i=n;i>=0;i--){
		while(deq.size() and deq.back().fi>=sp[i]) deq.pop_back();
		if(deq.size()) naj[i]=deq.back().se;
		else naj[i]=-1;
		deq.push_back({sp[i],i});
	}
	for(int i=1;i<=n;i++){
		if(sp[i]>sp[i-1]) upd(1,i,1);
		else upd(1,i,-1);
	}
	int curr=naj[0];
	while(curr!=-1){
		upd(1,curr,1);
		upd2(1,curr);
		curr=naj[curr];
	}
	int q;
	cin>>q;
	for(int i=1;i<=q;i++){
		int a,b;	
		cin>>a>>b;
		zap[a].push_back({b,i});
	}
	for(int i=1;i<=n;i++) single(i);
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 9 ms 12280 KB Output is correct
3 Correct 8 ms 12356 KB Output is correct
4 Correct 10 ms 12280 KB Output is correct
5 Correct 9 ms 12244 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 9 ms 12280 KB Output is correct
3 Correct 8 ms 12356 KB Output is correct
4 Correct 10 ms 12280 KB Output is correct
5 Correct 9 ms 12244 KB Output is correct
6 Correct 115 ms 17268 KB Output is correct
7 Correct 113 ms 16844 KB Output is correct
8 Correct 108 ms 16920 KB Output is correct
9 Correct 108 ms 17164 KB Output is correct
10 Correct 113 ms 17320 KB Output is correct
11 Correct 121 ms 17492 KB Output is correct
12 Correct 115 ms 17320 KB Output is correct
13 Correct 133 ms 17612 KB Output is correct
14 Correct 119 ms 17320 KB Output is correct
15 Correct 113 ms 17228 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 9 ms 12280 KB Output is correct
3 Correct 8 ms 12356 KB Output is correct
4 Correct 10 ms 12280 KB Output is correct
5 Correct 9 ms 12244 KB Output is correct
6 Correct 115 ms 17268 KB Output is correct
7 Correct 113 ms 16844 KB Output is correct
8 Correct 108 ms 16920 KB Output is correct
9 Correct 108 ms 17164 KB Output is correct
10 Correct 113 ms 17320 KB Output is correct
11 Correct 121 ms 17492 KB Output is correct
12 Correct 115 ms 17320 KB Output is correct
13 Correct 133 ms 17612 KB Output is correct
14 Correct 119 ms 17320 KB Output is correct
15 Correct 113 ms 17228 KB Output is correct
16 Correct 982 ms 50064 KB Output is correct
17 Correct 838 ms 46032 KB Output is correct
18 Correct 857 ms 47116 KB Output is correct
19 Correct 853 ms 48652 KB Output is correct
20 Correct 974 ms 49040 KB Output is correct
21 Correct 997 ms 51676 KB Output is correct
22 Correct 942 ms 49332 KB Output is correct
23 Correct 980 ms 50892 KB Output is correct
24 Correct 958 ms 49460 KB Output is correct
25 Correct 889 ms 47908 KB Output is correct