oj.uz

Submission #530353

# Submission time Handle Problem Language Result Execution time Memory
530353 2022-02-25T07:49:22 Z Koosha_mv Election (BOI18_election) C++14
100 / 100
 779 ms 45812 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=5e5+99;

int n,q,a[N],ans[N],seg[N<<2],lazy[N<<2];
vector<int> vec;
vector<pair<int,int>> Q[N];
string s;

void shift(int id){
	seg[id<<1]+=lazy[id];
	seg[id<<1|1]+=lazy[id];
	lazy[id<<1]+=lazy[id];
	lazy[id<<1|1]+=lazy[id];
	lazy[id]=0;
}
void build(int id=1,int l=1,int r=n+1){
	if(l+1==r){
		seg[id]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid,r);
	seg[id]=min(seg[id<<1],seg[id<<1|1]);
	//cout<<l<<" "<<r<<" "<<id<<endl;
}
void add(int L,int R,int val,int id=1,int l=1,int r=n+1){
	if(r<=L || R<=l) return ;
	if(L<=l && r<=R){
		seg[id]+=val;
		lazy[id]+=val;
		return ;
	}
	int mid=(l+r)>>1;
	shift(id);
	add(L,R,val,id<<1,l,mid);
	add(L,R,val,id<<1|1,mid,r);
	seg[id]=min(seg[id<<1],seg[id<<1|1]);
}
int get(int L,int R,int id=1,int l=1,int r=n+1){
	if(r<=L || R<=l) return N;
	if(L<=l && r<=R){
		return seg[id];
	}
	int mid=(l+r)>>1;
	shift(id);
	return min(get(L,R,id<<1,l,mid),get(L,R,id<<1|1,mid,r));
}

int main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>s>>q;
	s=' '+s;
	f(i,1,q+1){
		int l,r;
		cin>>l>>r;
		Q[r].pb(mp(l,i));
	}
	f(i,1,n+1){
		a[i]=a[i-1]+(s[i]=='C')-(s[i]=='T');
	}
	build();
	f(i,1,n+1){
		if(s[i]=='C'){
			if(vec.size()){
				add(vec.back(),n+1,-1);
				vec.pop_back();
			}
		}
		else{
			vec.pb(i);
			add(i,n+1,+1);
		}
		//dbgv(vec);
		for(auto p : Q[i]){
			int t=0;
			if(p.F-1) t=get(p.F-1,p.F);
			ans[p.S]=max(0,t-get(p.F,i+1));
			int l=-1,r=vec.size();
			while(l+1<r){
				int mid=(l+r)>>1;
				if(vec[mid]<p.F){
					l=mid;
				}
				else{
					r=mid;
				}
			}
			ans[p.S]+=vec.size()-r;
		}
	}
	f(i,1,q+1){
		cout<<ans[i]<<" ";
	}
}
/*
4
TCCT
1
1 4

11
CCCTTTTTTCC
1
4 9
*/

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12108 KB Output is correct
2 Correct 10 ms 12096 KB Output is correct
3 Correct 9 ms 12108 KB Output is correct
4 Correct 9 ms 12108 KB Output is correct
5 Correct 8 ms 12208 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12108 KB Output is correct
2 Correct 10 ms 12096 KB Output is correct
3 Correct 9 ms 12108 KB Output is correct
4 Correct 9 ms 12108 KB Output is correct
5 Correct 8 ms 12208 KB Output is correct
6 Correct 78 ms 17148 KB Output is correct
7 Correct 83 ms 16824 KB Output is correct
8 Correct 83 ms 16956 KB Output is correct
9 Correct 72 ms 17212 KB Output is correct
10 Correct 108 ms 17060 KB Output is correct
11 Correct 83 ms 17408 KB Output is correct
12 Correct 81 ms 17284 KB Output is correct
13 Correct 98 ms 17588 KB Output is correct
14 Correct 76 ms 17288 KB Output is correct
15 Correct 73 ms 17216 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12108 KB Output is correct
2 Correct 10 ms 12096 KB Output is correct
3 Correct 9 ms 12108 KB Output is correct
4 Correct 9 ms 12108 KB Output is correct
5 Correct 8 ms 12208 KB Output is correct
6 Correct 78 ms 17148 KB Output is correct
7 Correct 83 ms 16824 KB Output is correct
8 Correct 83 ms 16956 KB Output is correct
9 Correct 72 ms 17212 KB Output is correct
10 Correct 108 ms 17060 KB Output is correct
11 Correct 83 ms 17408 KB Output is correct
12 Correct 81 ms 17284 KB Output is correct
13 Correct 98 ms 17588 KB Output is correct
14 Correct 76 ms 17288 KB Output is correct
15 Correct 73 ms 17216 KB Output is correct
16 Correct 779 ms 43632 KB Output is correct
17 Correct 606 ms 40860 KB Output is correct
18 Correct 667 ms 41936 KB Output is correct
19 Correct 612 ms 43516 KB Output is correct
20 Correct 668 ms 42768 KB Output is correct
21 Correct 748 ms 45460 KB Output is correct
22 Correct 757 ms 44696 KB Output is correct
23 Correct 749 ms 45812 KB Output is correct
24 Correct 713 ms 45104 KB Output is correct
25 Correct 753 ms 43972 KB Output is correct