oj.uz

Submission #84513

# Submission time Handle Problem Language Result Execution time Memory
84513 2018-11-15T20:16:27 Z Pajaraja Election (BOI18_election) C++17
100 / 100
 1608 ms 148612 KB 
#include <bits/stdc++.h>
#define MAXN 500007
using namespace std;
string s;
int val[MAXN],t[2*MAXN],a[MAXN],ans[MAXN],seg[4*MAXN],bag[4*MAXN],n,bit[4*MAXN];
vector<pair<int,int> > u[MAXN];
vector<int> g[MAXN];
void updbit(int x,int val) {while(x<=n) {bit[x]+=val; x+=x&-x;} }
int calc(int x)
{
	int sol=0;
	while(x>0) {sol+=bit[x]; x-=x&-x;}
	return sol;
}
void relax(int ind)
{
	bag[2*ind]+=bag[ind];
	bag[2*ind+1]+=bag[ind];
	bag[ind]=0;
	seg[ind]=min(seg[2*ind]-bag[2*ind],seg[2*ind+1]-bag[2*ind+1]);
}
int nmin(int l,int r,int lt,int rt,int ind)
{
	if(l>rt || r<lt) return 1000000000;
	if(l>=lt && r<=rt) return seg[ind]-bag[ind];
	int s=(l+r)/2;
	relax(ind);
	return min(nmin(l,s,lt,rt,2*ind),nmin(s+1,r,lt,rt,2*ind+1));
}
void upd(int l,int r,int lt,int rt,int ind,int val)
{
	if(l>rt || r<lt) return;
	if(l>=lt && r<=rt) {bag[ind]+=val; return;}
	int s=(l+r)/2;
	upd(l,s,lt,rt,2*ind,val);
	upd(s+1,r,lt,rt,2*ind+1,val);
	relax(ind);
}
void napravi(int l,int r,int ind)
{
	if(l==r) {seg[ind]=val[l]; return;}
	int s=(l+r)/2;
	napravi(l,s,2*ind);
	napravi(s+1,r,2*ind+1);
	seg[ind]=min(seg[2*ind+1],seg[2*ind+1]);
}
void dfs(int s)
{
	if(s!=1) {upd(1,n+1,1,s-1,1,a[s-1]); updbit(s-1,1);}
	for(int i=0;i<g[s].size();i++) dfs(g[s][i]);
	for(int i=0;i<u[s].size();i++)
	{
		int r=u[s][i].first;
		ans[u[s][i].second]=max(0,nmin(1,n+1,r+1,r+1,1)-nmin(1,n+1,s,r,1))+calc(r)-calc(s-1);
	}
	if(s!=1) {upd(1,n+1,1,s-1,1,-a[s-1]); updbit(s-1,-1);}
}
int main()
{
	int q;
	cin>>n>>s>>q;
	for(int i=0;i<q;i++)
	{
		int l,r;
		cin>>l>>r;
		u[l].push_back(make_pair(r,i));
	}
	for(int i=0;i<n;i++) a[i+1]=s[i]=='T'?-1:1;
	int cur=MAXN;
	fill(t,t+2*MAXN,n+2);
	t[MAXN]=n+1;
	val[n+1]=MAXN;
	g[n+2].push_back(n+1);
	for(int i=n;i>0;i--)
	{
		cur+=a[i];
		val[i]=cur;
		g[t[cur+1]].push_back(i);
		t[cur]=i;
	}
	napravi(1,n+1,1);
	dfs(n+2);
	for(int i=0;i<q;i++) printf("%d\n",ans[i]);
}

Compilation message

election.cpp: In function 'void dfs(int)':
election.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) dfs(g[s][i]);
              ~^~~~~~~~~~~~
election.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u[s].size();i++)
              ~^~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 27896 KB Output is correct
2 Correct 30 ms 28020 KB Output is correct
3 Correct 31 ms 28136 KB Output is correct
4 Correct 31 ms 28364 KB Output is correct
5 Correct 29 ms 28364 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 27896 KB Output is correct
2 Correct 30 ms 28020 KB Output is correct
3 Correct 31 ms 28136 KB Output is correct
4 Correct 31 ms 28364 KB Output is correct
5 Correct 29 ms 28364 KB Output is correct
6 Correct 202 ms 35176 KB Output is correct
7 Correct 180 ms 35468 KB Output is correct
8 Correct 190 ms 36708 KB Output is correct
9 Correct 191 ms 37976 KB Output is correct
10 Correct 192 ms 38676 KB Output is correct
11 Correct 199 ms 40860 KB Output is correct
12 Correct 205 ms 41276 KB Output is correct
13 Correct 201 ms 43496 KB Output is correct
14 Correct 203 ms 43496 KB Output is correct
15 Correct 196 ms 43548 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 27896 KB Output is correct
2 Correct 30 ms 28020 KB Output is correct
3 Correct 31 ms 28136 KB Output is correct
4 Correct 31 ms 28364 KB Output is correct
5 Correct 29 ms 28364 KB Output is correct
6 Correct 202 ms 35176 KB Output is correct
7 Correct 180 ms 35468 KB Output is correct
8 Correct 190 ms 36708 KB Output is correct
9 Correct 191 ms 37976 KB Output is correct
10 Correct 192 ms 38676 KB Output is correct
11 Correct 199 ms 40860 KB Output is correct
12 Correct 205 ms 41276 KB Output is correct
13 Correct 201 ms 43496 KB Output is correct
14 Correct 203 ms 43496 KB Output is correct
15 Correct 196 ms 43548 KB Output is correct
16 Correct 1608 ms 82656 KB Output is correct
17 Correct 1545 ms 85672 KB Output is correct
18 Correct 1501 ms 94732 KB Output is correct
19 Correct 1359 ms 103824 KB Output is correct
20 Correct 1521 ms 110644 KB Output is correct
21 Correct 1588 ms 127248 KB Output is correct
22 Correct 1606 ms 129200 KB Output is correct
23 Correct 1557 ms 145356 KB Output is correct
24 Correct 1540 ms 146544 KB Output is correct
25 Correct 1557 ms 148612 KB Output is correct