oj.uz

Submission #486483

# Submission time Handle Problem Language Result Execution time Memory
486483 2021-11-11T19:38:19 Z MilosMilutinovic Election (BOI18_election) C++14
100 / 100
 1206 ms 28224 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=501000;
int n,q;
string s;

struct node {
	int pf,sf,s,f;
}nd[4*N];
node comb(node x,node y) {
	node ret;
	ret.pf=max(x.pf,x.s+y.pf);
	ret.sf=max(y.sf,y.s+x.sf);
	ret.s=x.s+y.s;
	ret.f=max({x.pf+y.sf,x.f+y.s,x.s+y.f});
	return ret;
}
void build(int p,int l,int r) {
	if (l==r) {
		if (s[l]=='T') {
			nd[p].pf=nd[p].sf=nd[p].s=nd[p].f=1;
		} else {
			nd[p].pf=nd[p].sf=nd[p].f=0;
			nd[p].s=-1;		
		}
	} else {
		int md=l+r>>1;
		build(p+p,l,md);
		build(p+p+1,md+1,r);
		nd[p]=comb(nd[p+p],nd[p+p+1]);
	}
}
node get(int p,int l,int r,int ql,int qr) {
	if (ql>r||qr<l) return {0,0,0,0};
	if (ql<=l&&r<=qr) return nd[p];
	int md=l+r>>1;
	return comb(get(p+p,l,md,ql,qr),get(p+p+1,md+1,r,ql,qr));
}

int main() {
	cin>>n;
	cin>>s;
	cin>>q;
	build(1,0,n-1);
	while (q--) {
		int l,r;
		cin>>l>>r;
		--l; --r;
		cout<<get(1,0,n-1,l,r).f<<"\n";
	}	
}

Compilation message

election.cpp: In function 'void build(int, int, int)':
election.cpp:47:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int md=l+r>>1;
      |          ~^~
election.cpp: In function 'node get(int, int, int, int, int)':
election.cpp:56:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |  int md=l+r>>1;
      |         ~^~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 4 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 152 ms 4780 KB Output is correct
7 Correct 146 ms 4772 KB Output is correct
8 Correct 166 ms 4748 KB Output is correct
9 Correct 141 ms 4676 KB Output is correct
10 Correct 150 ms 4820 KB Output is correct
11 Correct 151 ms 5048 KB Output is correct
12 Correct 149 ms 4872 KB Output is correct
13 Correct 149 ms 4928 KB Output is correct
14 Correct 149 ms 4892 KB Output is correct
15 Correct 149 ms 4932 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 4 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 152 ms 4780 KB Output is correct
7 Correct 146 ms 4772 KB Output is correct
8 Correct 166 ms 4748 KB Output is correct
9 Correct 141 ms 4676 KB Output is correct
10 Correct 150 ms 4820 KB Output is correct
11 Correct 151 ms 5048 KB Output is correct
12 Correct 149 ms 4872 KB Output is correct
13 Correct 149 ms 4928 KB Output is correct
14 Correct 149 ms 4892 KB Output is correct
15 Correct 149 ms 4932 KB Output is correct
16 Correct 1182 ms 26300 KB Output is correct
17 Correct 1135 ms 26612 KB Output is correct
18 Correct 1157 ms 26812 KB Output is correct
19 Correct 1083 ms 26292 KB Output is correct
20 Correct 1176 ms 26064 KB Output is correct
21 Correct 1180 ms 27772 KB Output is correct
22 Correct 1183 ms 27748 KB Output is correct
23 Correct 1202 ms 28224 KB Output is correct
24 Correct 1189 ms 27524 KB Output is correct
25 Correct 1206 ms 27096 KB Output is correct