oj.uz

Submission #234853

# Submission time Handle Problem Language Result Execution time Memory
234853 2020-05-26T03:45:57 Z mahmoudbadawy Election (BOI18_election) C++17
100 / 100
 1282 ms 44072 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=5e5+5;

int btree[4*N],lazy[4*N];
string s;
int n,q;
vector<pair<int,int> > qs[N];
int ans[N];

void prob(int node,int l,int r)
{
	btree[node]+=lazy[node];
	if(l!=r)
	{
		lazy[node<<1]+=lazy[node];
		lazy[(node<<1)|1]+=lazy[node];
	}
	lazy[node]=0;
}

void update(int node,int l,int r,int ql,int qr,int v)
{
	if(lazy[node]) prob(node,l,r);
	if(r<ql||qr<l) return;
	if(ql<=l&&r<=qr)
	{
		lazy[node]+=v;
		prob(node,l,r);
		return;
	}
	int mid=(l+r)>>1;
	update(node<<1,l,mid,ql,qr,v);
	update((node<<1)|1,mid+1,r,ql,qr,v);
	btree[node]=max(btree[node<<1],btree[(node<<1)|1]);
}

int query(int node,int l,int r,int ql,int qr)
{
	if(lazy[node]) prob(node,l,r);
	if(r<ql||qr<l) return -(1<<30);
	if(ql<=l&&r<=qr) return btree[node];
	int mid=(l+r)>>1;
	return max(query(node<<1,l,mid,ql,qr),query((node<<1)|1,mid+1,r,ql,qr));
}

int main()
{
	cin >> n >> s >> q;
	for(int i=0;i<q;i++)
	{
		int l,r;
		cin >> l >> r;
		l--; r--;
		qs[r].push_back({l,i});
	}
	vector<int> qp;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='T')
		{
			qp.push_back(i);
		}
		else
		{
			if(qp.size())
			{
				update(1,0,n-1,qp.back(),n,1);
				qp.pop_back();
			}
			update(1,0,n-1,i,n,-1);
		}
		for(auto j:qs[i])
		{
			int l=j.first;
			int x=lower_bound(qp.begin(),qp.end(),l)-qp.begin();
			ans[j.second]=(qp.size()-x)+max(query(1,0,n-1,l,i)-(l?query(1,0,n-1,l-1,l-1):0),0);
		}
	}
	for(int i=0;i<q;i++)
		printf("%d\n",ans[i]);
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12160 KB Output is correct
2 Correct 14 ms 12160 KB Output is correct
3 Correct 15 ms 12160 KB Output is correct
4 Correct 14 ms 12160 KB Output is correct
5 Correct 15 ms 12160 KB Output is correct
6 Correct 158 ms 17016 KB Output is correct
7 Correct 137 ms 16632 KB Output is correct
8 Correct 148 ms 16888 KB Output is correct
9 Correct 149 ms 17144 KB Output is correct
10 Correct 145 ms 16888 KB Output is correct
11 Correct 151 ms 17144 KB Output is correct
12 Correct 169 ms 17144 KB Output is correct
13 Correct 157 ms 17416 KB Output is correct
14 Correct 152 ms 17144 KB Output is correct
15 Correct 143 ms 17016 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12160 KB Output is correct
2 Correct 14 ms 12160 KB Output is correct
3 Correct 15 ms 12160 KB Output is correct
4 Correct 14 ms 12160 KB Output is correct
5 Correct 15 ms 12160 KB Output is correct
6 Correct 158 ms 17016 KB Output is correct
7 Correct 137 ms 16632 KB Output is correct
8 Correct 148 ms 16888 KB Output is correct
9 Correct 149 ms 17144 KB Output is correct
10 Correct 145 ms 16888 KB Output is correct
11 Correct 151 ms 17144 KB Output is correct
12 Correct 169 ms 17144 KB Output is correct
13 Correct 157 ms 17416 KB Output is correct
14 Correct 152 ms 17144 KB Output is correct
15 Correct 143 ms 17016 KB Output is correct
16 Correct 1259 ms 41904 KB Output is correct
17 Correct 1045 ms 39268 KB Output is correct
18 Correct 1133 ms 40368 KB Output is correct
19 Correct 1113 ms 41640 KB Output is correct
20 Correct 1236 ms 40828 KB Output is correct
21 Correct 1282 ms 43824 KB Output is correct
22 Correct 1245 ms 42920 KB Output is correct
23 Correct 1248 ms 44072 KB Output is correct
24 Correct 1254 ms 43300 KB Output is correct
25 Correct 1233 ms 42200 KB Output is correct