oj.uz

Submission #707369

# Submission time Handle Problem Language Result Execution time Memory
707369 2023-03-08T23:02:24 Z KLPP Election (BOI18_election) C++14
100 / 100
 688 ms 136804 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)

class ST{
	vector<array<lld,4>>arr;
	public:
	void init(int n){
		arr.resize(8*n,{0,0,0});
	}
	array<lld,4> combine(array<lld,4> A, array<lld,4> B){
		array<lld,4> C={A[0]+B[0],max(A[1],A[0]+B[1]),max(B[2],B[0]+A[2]),max(A[3],max(B[3],A[2]+B[1]))};
		return C;
	}
	void update(int a, int b, int node, int pos, lld val){
		if(pos<a || b<pos)return;
		if(a==b){
			arr[node]={val,max(0LL,val),max(0LL,val),max(0LL,val)};
			return;
		}
		int mid=(a+b)/2;
		update(a,mid,2*node,pos,val);
		update(mid+1,b,2*node+1,pos,val);
		arr[node]=combine(arr[2*node],arr[2*node+1]);
	}
	array<lld,4> query(int a, int b, int node, int l, int r){
		if(r<a || b<l){
			return {0,0,0,0};
		}
		if(l<=a && b<=r){
			return arr[node];
		}
		int mid=(a+b)/2;
		return combine(query(a,mid,2*node,l,r),query(mid+1,b,2*node+1,l,r));
	}
};

void solve(){
	/*freopen("cardgame.in", "r", stdin);
	freopen("cardgame.out", "w", stdout);*/
	int n,q;
	cin>>n;
	string s;
	cin>>s;
	cin>>q;
	ST S;
	S.init(n);
	rep(i,0,n){
		if(s[i]=='C')S.update(0,n-1,1,i,1);
		else S.update(0,n-1,1,i,-1);
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		l--;r--;
		array<lld,4> A=S.query(0,n-1,1,l,r);
		cout<<A[3]-A[0]<<"\n";
	}
}
	

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.precision(16);
	int tt=1;
	//cin>>tt;
	rep(test,0,tt){
		solve();
	}
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 71 ms 18272 KB Output is correct
7 Correct 61 ms 18360 KB Output is correct
8 Correct 57 ms 19140 KB Output is correct
9 Correct 57 ms 19156 KB Output is correct
10 Correct 76 ms 19044 KB Output is correct
11 Correct 66 ms 19316 KB Output is correct
12 Correct 72 ms 19296 KB Output is correct
13 Correct 69 ms 19344 KB Output is correct
14 Correct 61 ms 19276 KB Output is correct
15 Correct 66 ms 19176 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 71 ms 18272 KB Output is correct
7 Correct 61 ms 18360 KB Output is correct
8 Correct 57 ms 19140 KB Output is correct
9 Correct 57 ms 19156 KB Output is correct
10 Correct 76 ms 19044 KB Output is correct
11 Correct 66 ms 19316 KB Output is correct
12 Correct 72 ms 19296 KB Output is correct
13 Correct 69 ms 19344 KB Output is correct
14 Correct 61 ms 19276 KB Output is correct
15 Correct 66 ms 19176 KB Output is correct
16 Correct 601 ms 135732 KB Output is correct
17 Correct 583 ms 135408 KB Output is correct
18 Correct 575 ms 135640 KB Output is correct
19 Correct 507 ms 135056 KB Output is correct
20 Correct 610 ms 135000 KB Output is correct
21 Correct 610 ms 136680 KB Output is correct
22 Correct 573 ms 136556 KB Output is correct
23 Correct 584 ms 136804 KB Output is correct
24 Correct 688 ms 136548 KB Output is correct
25 Correct 612 ms 136020 KB Output is correct