oj.uz

Submission #571985

# Submission time Handle Problem Language Result Execution time Memory
571985 2022-06-03T08:36:26 Z duytuandao21 Election (BOI18_election) C++17
100 / 100
 587 ms 20320 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(x.minl + y.minr, max(x.sum + y.minimum_result, x.minimum_result + y.sum)), 
		x.sum + y.sum, 
		max(x.minl, x.sum + y.minl),
		max(y.minr, y.sum + x.minr)
	};
}
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);
	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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 400 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 64 ms 4804 KB Output is correct
7 Correct 59 ms 4876 KB Output is correct
8 Correct 61 ms 4812 KB Output is correct
9 Correct 57 ms 4712 KB Output is correct
10 Correct 67 ms 4752 KB Output is correct
11 Correct 62 ms 4876 KB Output is correct
12 Correct 60 ms 4844 KB Output is correct
13 Correct 75 ms 4960 KB Output is correct
14 Correct 68 ms 4828 KB Output is correct
15 Correct 66 ms 4764 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 64 ms 4804 KB Output is correct
7 Correct 59 ms 4876 KB Output is correct
8 Correct 61 ms 4812 KB Output is correct
9 Correct 57 ms 4712 KB Output is correct
10 Correct 67 ms 4752 KB Output is correct
11 Correct 62 ms 4876 KB Output is correct
12 Correct 60 ms 4844 KB Output is correct
13 Correct 75 ms 4960 KB Output is correct
14 Correct 68 ms 4828 KB Output is correct
15 Correct 66 ms 4764 KB Output is correct
16 Correct 587 ms 19300 KB Output is correct
17 Correct 462 ms 19284 KB Output is correct
18 Correct 509 ms 19288 KB Output is correct
19 Correct 460 ms 18796 KB Output is correct
20 Correct 524 ms 18372 KB Output is correct
21 Correct 562 ms 20064 KB Output is correct
22 Correct 543 ms 20116 KB Output is correct
23 Correct 578 ms 20320 KB Output is correct
24 Correct 573 ms 19944 KB Output is correct
25 Correct 544 ms 19444 KB Output is correct