oj.uz

Submission #584346

# Submission time Handle Problem Language Result Execution time Memory
584346 2022-06-27T08:42:05 Z codr0 Election (BOI18_election) C++14
100 / 100
 547 ms 27952 KB 
// Code by Parsa Eslami
     
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>

#define bit(i,j) ((j>>i)&1)
#define minm(x,y) x=min(x,y)
#define maxm(x,y) x=max(x,y)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n'
#define wtf cout<<"WHAT THE FUCK!\n"
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1

using namespace std;
const int N=5e5+4;
struct node{
	int sum,pr,sf,ans;
};
node seg[4*N];
node emp;

	node merge(node a,node b){
		node rt;
		rt.sum=a.sum+b.sum;
		rt.pr=max(a.pr,a.sum+b.pr);
		rt.sf=max(a.sf+b.sum,b.sf);
		rt.ans=max(a.ans+b.sum,b.ans+a.sum);
		maxm(rt.ans,a.pr+b.sf);
		return rt;
	}

	void upd(int id,int l,int r,int ind,int x){
		if(l>ind||r<=ind) return;
		if(l+1==r){
			seg[id].ans=max(0,x);
			seg[id].sf=max(0,x);
			seg[id].pr=max(0,x);
			seg[id].sum=x;
			return;
		}
		dmid;
		upd(lc,l,mid,ind,x);
		upd(rc,mid,r,ind,x);
		seg[id]=merge(seg[lc],seg[rc]);
	}

	node get(int id,int l,int r,int st,int en){
		if(st>=r||en<=l) return emp;
		if(st<=l&&en>=r) return seg[id];
		dmid;
		return merge(get(lc,l,mid,st,en),get(rc,mid,r,st,en));
	}

	int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0);	

	int n; cin>>n;
	string s; cin>>s;
	s='$'+s;
	FOR(i,1,n){
		if(s[i]=='C') upd(1,1,n+1,i,-1);
		else upd(1,1,n+1,i,+1);
	}
	int q; cin>>q;
	while(q--){
		int l,r; cin>>l>>r;
		cout<<get(1,1,n+1,l,r+1).ans<<'\n';
	}

	return 0;
    }

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 56 ms 4804 KB Output is correct
7 Correct 56 ms 5256 KB Output is correct
8 Correct 54 ms 5644 KB Output is correct
9 Correct 57 ms 5708 KB Output is correct
10 Correct 54 ms 5688 KB Output is correct
11 Correct 57 ms 5768 KB Output is correct
12 Correct 55 ms 5780 KB Output is correct
13 Correct 58 ms 5848 KB Output is correct
14 Correct 55 ms 5864 KB Output is correct
15 Correct 71 ms 5836 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 56 ms 4804 KB Output is correct
7 Correct 56 ms 5256 KB Output is correct
8 Correct 54 ms 5644 KB Output is correct
9 Correct 57 ms 5708 KB Output is correct
10 Correct 54 ms 5688 KB Output is correct
11 Correct 57 ms 5768 KB Output is correct
12 Correct 55 ms 5780 KB Output is correct
13 Correct 58 ms 5848 KB Output is correct
14 Correct 55 ms 5864 KB Output is correct
15 Correct 71 ms 5836 KB Output is correct
16 Correct 506 ms 26956 KB Output is correct
17 Correct 460 ms 26560 KB Output is correct
18 Correct 497 ms 26788 KB Output is correct
19 Correct 444 ms 26264 KB Output is correct
20 Correct 519 ms 26052 KB Output is correct
21 Correct 540 ms 27940 KB Output is correct
22 Correct 527 ms 27684 KB Output is correct
23 Correct 527 ms 27952 KB Output is correct
24 Correct 517 ms 27632 KB Output is correct
25 Correct 547 ms 27112 KB Output is correct