oj.uz

Submission #486482

# Submission time Handle Problem Language Result Execution time Memory
486482 2021-11-11T19:37:56 Z MilosMilutinovic Election (BOI18_election) C++14
82 / 100
 159 ms 5828 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=101000;
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 5 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 5 ms 332 KB Output is correct
6 Correct 149 ms 5700 KB Output is correct
7 Correct 144 ms 5740 KB Output is correct
8 Correct 147 ms 5616 KB Output is correct
9 Correct 151 ms 5728 KB Output is correct
10 Correct 145 ms 5636 KB Output is correct
11 Correct 153 ms 5828 KB Output is correct
12 Correct 148 ms 5776 KB Output is correct
13 Correct 147 ms 5828 KB Output is correct
14 Correct 151 ms 5828 KB Output is correct
15 Correct 159 ms 5768 KB Output is correct

Subtask #3
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 5 ms 332 KB Output is correct
6 Correct 149 ms 5700 KB Output is correct
7 Correct 144 ms 5740 KB Output is correct
8 Correct 147 ms 5616 KB Output is correct
9 Correct 151 ms 5728 KB Output is correct
10 Correct 145 ms 5636 KB Output is correct
11 Correct 153 ms 5828 KB Output is correct
12 Correct 148 ms 5776 KB Output is correct
13 Correct 147 ms 5828 KB Output is correct
14 Correct 151 ms 5828 KB Output is correct
15 Correct 159 ms 5768 KB Output is correct
16 Runtime error 11 ms 2308 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -