oj.uz

Submission #624772

# Submission time Handle Problem Language Result Execution time Memory
624772 2022-08-08T17:51:01 Z NintsiChkhaidze Election (BOI18_election) C++14
82 / 100
 139 ms 20012 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 = 200005;
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 3 ms 424 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 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 3 ms 424 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 124 ms 5776 KB Output is correct
7 Correct 132 ms 5664 KB Output is correct
8 Correct 131 ms 5716 KB Output is correct
9 Correct 95 ms 5748 KB Output is correct
10 Correct 116 ms 5596 KB Output is correct
11 Correct 129 ms 5940 KB Output is correct
12 Correct 134 ms 5860 KB Output is correct
13 Correct 117 ms 5900 KB Output is correct
14 Correct 126 ms 5856 KB Output is correct
15 Correct 139 ms 5760 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 424 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 124 ms 5776 KB Output is correct
7 Correct 132 ms 5664 KB Output is correct
8 Correct 131 ms 5716 KB Output is correct
9 Correct 95 ms 5748 KB Output is correct
10 Correct 116 ms 5596 KB Output is correct
11 Correct 129 ms 5940 KB Output is correct
12 Correct 134 ms 5860 KB Output is correct
13 Correct 117 ms 5900 KB Output is correct
14 Correct 126 ms 5856 KB Output is correct
15 Correct 139 ms 5760 KB Output is correct
16 Runtime error 17 ms 20012 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -