oj.uz

Submission #69563

# Submission time Handle Problem Language Result Execution time Memory
69563 2018-08-21T09:00:19 Z khohko Election (BOI18_election) C++17
100 / 100
 2789 ms 148928 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e9+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e6+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;

ll n;
ll m,k;
vector<ll> v[ARRS];
ll f[ARRS];
ll a[ARRS];
ll sm[ARRS];
ll ct[ARRS];

ll sum(ll l,ll r){
	return sm[r]-sm[l-1];
}

struct node{
	node *L,*R;
	ll u,d,s,sm;
	node(){
		L=R=NULL;
		u=0;
		d=0;
		s=0;
		sm=0;
	}
	void updt(){
		node a=*L;
		node b=*R;
		sm=a.sm+b.sm;
		///////
		u=max(a.u,b.u+a.sm);
		d=max(b.d,a.d+b.sm);

		b.u=max(0ll,a.sm+b.u-a.u);
		a.d=max(0ll,b.sm+a.d-b.d);

		s=min(b.s,b.u)+
			min(a.s,a.d)+
			max(0ll,min(b.u-b.s,a.d-a.s));
	}
};

node join(node a,node b){
	node x;
	x.sm=a.sm+b.sm;
///////
	x.u=max(a.u,b.u+a.sm);
	x.d=max(b.d,a.d+b.sm);

	b.u=max(0ll,a.sm+b.u-a.u);
	a.d=max(0ll,b.sm+a.d-b.d);
	x.s=min(b.s,b.u)+
			min(a.s,a.d)+
				max(0ll,min(b.u-b.s,a.d-a.s));



	return x;
}

void init(ll l,ll r,node *& x){
	if(!x)x=new node();
	if(l==r-1){
		if(a[l]==1){
			x->u=0;
			x->d=0;
			x->s=0;
			x->sm=-1;
		}
		else {
			x->u=1;
			x->d=1;
			x->s=1;
			x->sm=1;
		}
		return;
	}
	init(l,l+r>>1,x->L);
	init(l+r>>1,r,x->R);
	x->updt();
//	cout<<l<<" "<<r<<" "<<x->u<<" "<<x->d<<" "<<x->s<<" "<<x->sm<<endl;
}
node pas;
ll wl,wr;
void quer(ll l,ll r,node *& x){
	if(wr<l||r-1<wl)return;
	if(wl<=l&&r-1<=wr){
		pas=join(pas,*x);
		return;
	}
	quer(l,l+r>>1,x->L);
	quer(l+r>>1,r,x->R);
}

node *rt=NULL;
int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	ios::sync_with_stdio(0);
	ll n;
	string s;
	cin>>n>>s;
	for(int i=1; i<=n; i++){
		if(s[i-1]=='C')a[i]=1;
		else a[i]=-1;
	}

	ll q,l,r;
	init(1,n+1,rt);
	cin>>q;
	while(q--){
		cin>>wl>>wr;
		pas=*(new node());
		quer(1,n+1,rt);
		cout<<pas.u+pas.d-pas.s<<endl;
	}
}

Compilation message

election.cpp: In function 'void init(long long int, long long int, node*&)':
election.cpp:92:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  init(l,l+r>>1,x->L);
         ~^~
election.cpp:93:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  init(l+r>>1,r,x->R);
       ~^~
election.cpp: In function 'void quer(long long int, long long int, node*&)':
election.cpp:105:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  quer(l,l+r>>1,x->L);
         ~^~
election.cpp:106:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  quer(l+r>>1,r,x->R);
       ~^~
election.cpp: In function 'int main()':
election.cpp:124:7: warning: unused variable 'l' [-Wunused-variable]
  ll q,l,r;
       ^
election.cpp:124:9: warning: unused variable 'r' [-Wunused-variable]
  ll q,l,r;
         ^

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 47736 KB Output is correct
2 Correct 50 ms 47736 KB Output is correct
3 Correct 49 ms 47916 KB Output is correct
4 Correct 47 ms 47916 KB Output is correct
5 Correct 54 ms 47916 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 47736 KB Output is correct
2 Correct 50 ms 47736 KB Output is correct
3 Correct 49 ms 47916 KB Output is correct
4 Correct 47 ms 47916 KB Output is correct
5 Correct 54 ms 47916 KB Output is correct
6 Correct 304 ms 61608 KB Output is correct
7 Correct 299 ms 61608 KB Output is correct
8 Correct 291 ms 61608 KB Output is correct
9 Correct 310 ms 61608 KB Output is correct
10 Correct 300 ms 61608 KB Output is correct
11 Correct 311 ms 61752 KB Output is correct
12 Correct 288 ms 61752 KB Output is correct
13 Correct 324 ms 61752 KB Output is correct
14 Correct 299 ms 61788 KB Output is correct
15 Correct 285 ms 61788 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 47736 KB Output is correct
2 Correct 50 ms 47736 KB Output is correct
3 Correct 49 ms 47916 KB Output is correct
4 Correct 47 ms 47916 KB Output is correct
5 Correct 54 ms 47916 KB Output is correct
6 Correct 304 ms 61608 KB Output is correct
7 Correct 299 ms 61608 KB Output is correct
8 Correct 291 ms 61608 KB Output is correct
9 Correct 310 ms 61608 KB Output is correct
10 Correct 300 ms 61608 KB Output is correct
11 Correct 311 ms 61752 KB Output is correct
12 Correct 288 ms 61752 KB Output is correct
13 Correct 324 ms 61752 KB Output is correct
14 Correct 299 ms 61788 KB Output is correct
15 Correct 285 ms 61788 KB Output is correct
16 Correct 2601 ms 148016 KB Output is correct
17 Correct 2153 ms 148016 KB Output is correct
18 Correct 2337 ms 148096 KB Output is correct
19 Correct 1953 ms 148096 KB Output is correct
20 Correct 2645 ms 148096 KB Output is correct
21 Correct 2579 ms 148800 KB Output is correct
22 Correct 2789 ms 148832 KB Output is correct
23 Correct 2522 ms 148928 KB Output is correct
24 Correct 2727 ms 148928 KB Output is correct
25 Correct 2394 ms 148928 KB Output is correct