oj.uz

Submission #956556

# Submission time Handle Problem Language Result Execution time Memory
956556 2024-04-02T07:06:09 Z moonrabbit2 Election (BOI18_election) C++17
100 / 100
 541 ms 54076 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using pii=array<int,2>;
using tii=array<int,3>;
const int N=500005;
int n,a[N],s[N],q,ans[N],pos[2*N];
vector<pii> qry[N];
string S;
struct ST{
	tii T[2*N];
	tii mrg(tii L,tii R){
		return tii{min(L[0]+R[1],R[0]),L[1]+R[1],L[2]+R[2]};
	}
	void init(int nd,int l,int r){
		T[nd]={0,0,r-l+1};
		if(l==r) return;
		int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
		init(ln,l,m); init(rn,m+1,r);
	}
	void upd(int nd,int l,int r,int x,int v){
		if(l==r){
			T[nd]={min(0,v),v,v==0};
			return;
		}
		int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
		if(x<=m) upd(ln,l,m,x,v);
		else upd(rn,m+1,r,x,v);
		T[nd]=mrg(T[ln],T[rn]);
	}
	tii qry(int nd,int l,int r,int s,int e){
		if(s<=l&&r<=e) return T[nd];
		int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
		if(e<=m) return qry(ln,l,m,s,e);
		if(m+1<=s) return qry(rn,m+1,r,s,e);
		return mrg(qry(ln,l,m,s,e),qry(rn,m+1,r,s,e));
	}
}T;
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>S>>q;
	for(int i=1;i<=n;i++){
		if(S[i-1]=='C') a[i]=1;
		else a[i]=-1;
		s[i]=s[i-1]+a[i];
	}
	for(int l,r,i=1;i<=q;i++){
		cin>>l>>r;
		qry[l].push_back({i,r});
	}
	T.init(1,1,n);
	for(int i=n;i>=1;i--){
		if(pos[s[i]+n]) T.upd(1,1,n,pos[s[i]+n],a[pos[s[i]+n]]);
		pos[s[i]+n]=i;
		if(a[i]>0){
			T.upd(1,1,n,i,a[i]);
			if(pos[s[i]-1+n]) T.upd(1,1,n,pos[s[i]-1+n],a[pos[s[i]-1+n]]);			
		}
		for(auto [idx,j]: qry[i]){
			tii Q=T.qry(1,1,n,i,j);
			ans[idx]=-Q[0]+Q[2];
		}
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
	/*
		int s=0,ans=0,mn=0;
		for(int i=l;i<=r;i++){
			s+=a[i];
			if(s<mn){
				chk[i]=1;
				mn=s;
				ans++;
			} else{
				chk[i]=0;
			}
		}
		s=mn=0;
		for(int i=r;i>=l;i--) if(!chk[i]){
			s+=a[i];
			mn=min(mn,s);
		}
		ans-=mn;
		cout<<ans<<"\n";
	}*/
	return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21084 KB Output is correct
2 Correct 6 ms 21084 KB Output is correct
3 Correct 6 ms 21084 KB Output is correct
4 Correct 8 ms 21084 KB Output is correct
5 Correct 6 ms 21336 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21084 KB Output is correct
2 Correct 6 ms 21084 KB Output is correct
3 Correct 6 ms 21084 KB Output is correct
4 Correct 8 ms 21084 KB Output is correct
5 Correct 6 ms 21336 KB Output is correct
6 Correct 54 ms 25936 KB Output is correct
7 Correct 50 ms 25412 KB Output is correct
8 Correct 62 ms 25472 KB Output is correct
9 Correct 45 ms 25784 KB Output is correct
10 Correct 49 ms 25676 KB Output is correct
11 Correct 61 ms 26104 KB Output is correct
12 Correct 47 ms 25872 KB Output is correct
13 Correct 45 ms 25812 KB Output is correct
14 Correct 49 ms 25936 KB Output is correct
15 Correct 64 ms 25932 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21084 KB Output is correct
2 Correct 6 ms 21084 KB Output is correct
3 Correct 6 ms 21084 KB Output is correct
4 Correct 8 ms 21084 KB Output is correct
5 Correct 6 ms 21336 KB Output is correct
6 Correct 54 ms 25936 KB Output is correct
7 Correct 50 ms 25412 KB Output is correct
8 Correct 62 ms 25472 KB Output is correct
9 Correct 45 ms 25784 KB Output is correct
10 Correct 49 ms 25676 KB Output is correct
11 Correct 61 ms 26104 KB Output is correct
12 Correct 47 ms 25872 KB Output is correct
13 Correct 45 ms 25812 KB Output is correct
14 Correct 49 ms 25936 KB Output is correct
15 Correct 64 ms 25932 KB Output is correct
16 Correct 541 ms 52240 KB Output is correct
17 Correct 390 ms 48352 KB Output is correct
18 Correct 392 ms 49636 KB Output is correct
19 Correct 406 ms 50836 KB Output is correct
20 Correct 452 ms 51800 KB Output is correct
21 Correct 491 ms 53468 KB Output is correct
22 Correct 509 ms 53308 KB Output is correct
23 Correct 466 ms 54076 KB Output is correct
24 Correct 495 ms 53480 KB Output is correct
25 Correct 477 ms 53524 KB Output is correct