oj.uz

Submission #571984

# Submission time Handle Problem Language Result Execution time Memory
571984 2022-06-03T08:35:46 Z duytuandao21 Election (BOI18_election) C++17
100 / 100
 608 ms 28016 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+7;
int n,q,m,a[N]; 
string s;
struct node {
	int minimum_result;
	int sum;
	int minl;
	int minr;
};
node seg[N];
node join(node x, node y) {
	return {
		//max(l.l + r.r, max(l.s + r.a, l.a + r.s))
		max(x.minl + y.minr, max(x.sum + y.minimum_result, x.minimum_result + y.sum)), 
		x.sum + y.sum, 
		//l.s + r.s
		max(x.minl, x.sum + y.minl),
		//max(l.l, l.s + r.l)
		max(y.minr, y.sum + x.minr)
		//max(l.r + r.s, r.r))
	};
}
void build(int id,int l,int r, int pos, int val) {
	if(l > r || r < pos || l > pos) return;
	if(l == r) {
		seg[id].sum = val;
		seg[id].minl = max(seg[id].minl, val);
		seg[id].minr = max(seg[id].minr, val);
		seg[id].minimum_result = max(seg[id].minimum_result, val);
		return;
	}
	int mid = (l + r) / 2;
	build(id*2,l,mid,pos,val);
	build(id*2+1,mid+1,r,pos,val);
	seg[id] = join(seg[id*2], seg[id*2+1]);
}
node get(int id,int l,int r,int u,int v) {
	if(l > v || r < u) return {0,0,0,0};
	if(l >= u && r <= v) return seg[id];
	int mid = (l + r) / 2;
	return join(get(id*2,l,mid,u,v), get(id*2+1,mid+1,r,u,v));
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>s>>q;
	for(int i=0;i<n;i++) if(s[i] == 'C') build(1,1,n,i+1,-1); else build(1,1,n,i+1,1);
	//build(1,1,n);
	while(q--) {
		int l,r;
		cin>>l>>r;
		cout<<get(1,1,n,l,r).minimum_result<<'\n';
	}
	return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 424 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 66 ms 5868 KB Output is correct
7 Correct 73 ms 5752 KB Output is correct
8 Correct 59 ms 5744 KB Output is correct
9 Correct 60 ms 5740 KB Output is correct
10 Correct 58 ms 5648 KB Output is correct
11 Correct 62 ms 5836 KB Output is correct
12 Correct 61 ms 5848 KB Output is correct
13 Correct 71 ms 5924 KB Output is correct
14 Correct 58 ms 5836 KB Output is correct
15 Correct 58 ms 5708 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 66 ms 5868 KB Output is correct
7 Correct 73 ms 5752 KB Output is correct
8 Correct 59 ms 5744 KB Output is correct
9 Correct 60 ms 5740 KB Output is correct
10 Correct 58 ms 5648 KB Output is correct
11 Correct 62 ms 5836 KB Output is correct
12 Correct 61 ms 5848 KB Output is correct
13 Correct 71 ms 5924 KB Output is correct
14 Correct 58 ms 5836 KB Output is correct
15 Correct 58 ms 5708 KB Output is correct
16 Correct 608 ms 26988 KB Output is correct
17 Correct 540 ms 26576 KB Output is correct
18 Correct 531 ms 26760 KB Output is correct
19 Correct 482 ms 26388 KB Output is correct
20 Correct 547 ms 26092 KB Output is correct
21 Correct 568 ms 27884 KB Output is correct
22 Correct 553 ms 27748 KB Output is correct
23 Correct 533 ms 28016 KB Output is correct
24 Correct 592 ms 27600 KB Output is correct
25 Correct 551 ms 27276 KB Output is correct