oj.uz

Submission #647647

# Submission time Handle Problem Language Result Execution time Memory
647647 2022-10-03T13:12:10 Z Autron Election (BOI18_election) C++14
100 / 100
 1383 ms 71428 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define mid ((l+r)/2)
#define ls (2*cr)
#define rs (2*cr+1)
struct segmentTree{
	struct data{
		int pref, suf, sum, sol;
	};
	data join(data a, data b){
		data ret;
		ret.pref=max(a.pref, a.sum+b.pref);
		ret.suf=max(a.suf+b.sum, b.suf);
		ret.sum=a.sum+b.sum;
		ret.sol=max({a.pref+b.suf, a.sol+b.sum, a.sum+b.sol});
		return ret;
	}
	int n;
	vector<data> v;

	segmentTree(int _n){
		n=_n;
		v.resize(4*n+2);
	}

	void build(string &val, int l, int r, int cr){
		if(l==r){
			if(val[l]=='C') v[cr].pref=0, v[cr].suf=0, v[cr].sol=0, v[cr].sum=-1;
			else v[cr].pref=1, v[cr].suf=1, v[cr].sol=1, v[cr].sum=1;
		}
		else{
			build(val, l, mid, ls);
			build(val, mid+1, r, rs);
			v[cr]=join(v[ls], v[rs]);
		}
	}
	void build(string &val){
		build(val, 1, n, 1);
	}
	

	data query(int ql, int qr, int l, int r, int cr){
		if(ql==l&&qr==r){
			return v[cr];
		}
		else{
			if(qr<=mid) return query(ql, qr, l, mid, ls);
			if(mid<ql) return query(ql, qr, mid+1, r, rs);
			return join(query(ql, mid, l, mid, ls), query(mid+1, qr, mid+1, r, rs));
		}
	}

	int query(int l, int r){
		return query(l, r, 1, n, 1).sol;
	}
};
#undef mid 
#undef ls
#undef rs


int32_t main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	s='$'+s;
	segmentTree aint=segmentTree(n);
	aint.build(s);
	int q;
	cin>>q;
	while(q--){
		int l, r;
		cin>>l>>r;
		cout<<aint.query(l, r)<<"\n";
	}
	return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 596 KB Output is correct
2 Correct 5 ms 596 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 6 ms 568 KB Output is correct
5 Correct 5 ms 596 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 596 KB Output is correct
2 Correct 5 ms 596 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 6 ms 568 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 178 ms 10400 KB Output is correct
7 Correct 162 ms 10288 KB Output is correct
8 Correct 167 ms 10440 KB Output is correct
9 Correct 160 ms 10420 KB Output is correct
10 Correct 184 ms 10264 KB Output is correct
11 Correct 174 ms 10624 KB Output is correct
12 Correct 166 ms 10584 KB Output is correct
13 Correct 163 ms 10564 KB Output is correct
14 Correct 180 ms 10420 KB Output is correct
15 Correct 161 ms 10568 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 596 KB Output is correct
2 Correct 5 ms 596 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 6 ms 568 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 178 ms 10400 KB Output is correct
7 Correct 162 ms 10288 KB Output is correct
8 Correct 167 ms 10440 KB Output is correct
9 Correct 160 ms 10420 KB Output is correct
10 Correct 184 ms 10264 KB Output is correct
11 Correct 174 ms 10624 KB Output is correct
12 Correct 166 ms 10584 KB Output is correct
13 Correct 163 ms 10564 KB Output is correct
14 Correct 180 ms 10420 KB Output is correct
15 Correct 161 ms 10568 KB Output is correct
16 Correct 1317 ms 70344 KB Output is correct
17 Correct 1323 ms 70392 KB Output is correct
18 Correct 1278 ms 70460 KB Output is correct
19 Correct 1213 ms 69920 KB Output is correct
20 Correct 1383 ms 69464 KB Output is correct
21 Correct 1322 ms 71180 KB Output is correct
22 Correct 1331 ms 71220 KB Output is correct
23 Correct 1330 ms 71428 KB Output is correct
24 Correct 1314 ms 71048 KB Output is correct
25 Correct 1334 ms 70464 KB Output is correct