oj.uz

Submission #624773

# Submission time Handle Problem Language Result Execution time Memory
624773 2022-08-08T17:51:41 Z NintsiChkhaidze Election (BOI18_election) C++14
100 / 100
 1089 ms 28112 KB 
#include <bits/stdc++.h>
#define pb push_back
#define tree int h,int l,int r
#define left (h<<1),l,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int N = 500005;
string s;

struct {
	int l = 0; // max prefix sum
	int r = 0; // max suffix sum
	int s = 0; 
	int ans = 0; 
} t[4*N];
void UPDnode(int h){
	t[h].s = t[h*2].s + t[h*2 + 1].s;
	
	t[h].l = max(t[h*2].l,t[h*2].s + t[h*2 + 1].l);
	t[h].r = max(t[h*2 + 1].r,t[h*2].r + t[h*2+1].s);
	
	t[h].ans = max({t[h*2].ans + t[h*2+1].s,t[h*2+1].ans + t[h*2].s,t[h*2].l + t[h*2 + 1].r});
}
void U(int h,int l){
	if (s[l] == 'C') {
		t[h].ans = t[h].l = 0,t[h].r = 0;
		t[h].s = -1;
	}else{
		t[h].s = t[h].ans = t[h].l = t[h].r = 1;
	}
}
void build(tree){
	if (l == r){
		U(h,l);	
		return;
	}
	build(left);
	build(right);
	UPDnode(h);
}

vector <int> get(tree,int L,int R){
	if (r < L || R < l) return {0,0,0,0};
	if (L <= l && r <= R) return {t[h].l,t[h].r,t[h].s,t[h].ans};
	vector <int> x = get(left,L,R),y = get(right,L,R),z = {0,0,0,0};
	z[2] = x[2] + y[2];
	z[0] = max(x[0],x[2] + y[0]);
	z[1] = max(y[1],x[1] + y[2]);
	z[3] = max({x[3] + y[2],y[3] + x[2],x[0] + y[1]});
	return z;
}
main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n;
	cin>>n;
	cin>>s;
	s='%' + s;
	
	build(1,1,n);
	int m;
	cin>>m;
	for (int i = 1; i <= m; i++){
		int l,r;
		cin>>l>>r;
		vector <int> res = get(1,1,n,l,r);
		cout<<res[3]<<"\n";
	}
	
}

Compilation message

election.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main (){
      | ^~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 404 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 2 ms 404 KB Output is correct
5 Correct 3 ms 340 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 3 ms 404 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 2 ms 404 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 121 ms 4936 KB Output is correct
7 Correct 120 ms 4788 KB Output is correct
8 Correct 124 ms 4716 KB Output is correct
9 Correct 95 ms 4792 KB Output is correct
10 Correct 122 ms 4680 KB Output is correct
11 Correct 118 ms 4844 KB Output is correct
12 Correct 125 ms 4892 KB Output is correct
13 Correct 114 ms 4948 KB Output is correct
14 Correct 120 ms 4916 KB Output is correct
15 Correct 123 ms 4836 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 3 ms 404 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 2 ms 404 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 121 ms 4936 KB Output is correct
7 Correct 120 ms 4788 KB Output is correct
8 Correct 124 ms 4716 KB Output is correct
9 Correct 95 ms 4792 KB Output is correct
10 Correct 122 ms 4680 KB Output is correct
11 Correct 118 ms 4844 KB Output is correct
12 Correct 125 ms 4892 KB Output is correct
13 Correct 114 ms 4948 KB Output is correct
14 Correct 120 ms 4916 KB Output is correct
15 Correct 123 ms 4836 KB Output is correct
16 Correct 1086 ms 26340 KB Output is correct
17 Correct 1038 ms 26708 KB Output is correct
18 Correct 1065 ms 26896 KB Output is correct
19 Correct 864 ms 26452 KB Output is correct
20 Correct 1063 ms 26092 KB Output is correct
21 Correct 1087 ms 27964 KB Output is correct
22 Correct 1082 ms 27668 KB Output is correct
23 Correct 1083 ms 28112 KB Output is correct
24 Correct 1075 ms 27688 KB Output is correct
25 Correct 1089 ms 27292 KB Output is correct