oj.uz

Submission #735293

# Submission time Handle Problem Language Result Execution time Memory
735293 2023-05-03T20:59:26 Z MODDI Election (BOI18_election) C++14
100 / 100
 1595 ms 27872 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n;
string str;
struct state{
	int ans;
	int tot;
	int pref;
	int suf;
};
state neutral;
state tree[4 * 500100];
state merge(state a, state b){
    if(a.tot==-(1e9))return b;if(b.tot==-(1e9))return a;
    state c;
    c.tot=a.tot+b.tot;
    c.pref=std::max(a.tot+b.pref,a.pref);
    c.suf=std::max(b.tot+a.suf,b.suf);
    c.ans=std::max(std::max(a.ans+b.tot,a.tot+b.ans),a.pref+b.suf);
    return c;
}
void update(int node, int l, int r, state put, int pos){
	if(l == r && l == pos){
		tree[node] = put;
	}
	else{
		int mid = (l + r) / 2;
		if(pos <= mid)	update(node*2, l, mid, put, pos);
		else	update(node*2+1, mid+1, r, put, pos);
		
		tree[node] =merge(tree[node*2], tree[node*2+1]);
	}
}
state query(int node, int l, int r, int L, int R){
	if(r < L || l > R)	return neutral;
	if(L <= l && r <= R)	return tree[node];
	
	int mid = (l + r) / 2;
	return merge(query(node*2, l, mid, L, R), query(node*2+1, mid+1, r, L, R));
}
int main(){
	cin>>n>>str;
	state neg, pos;
	neg.ans = neg.pref = neg.suf = neg.tot = 1;
	pos.ans = pos.pref = pos.suf = 0;
	pos.tot = -1;
	neutral.tot = -1e9;
	for(int i = 0; i < n; i++){
		if(str[i] == 'C')	update(1, 0, n-1, pos, i);
		else update(1, 0, n-1, neg, i);
	}
	int q;
	cin>>q;
	while(q--){
		int l, r;
		cin>>l>>r;
		l--; r--;
		cout<<query(1, 0, n-1, l, r).ans<<endl;
	}
	return 0;
}

Compilation message

election.cpp: In function 'state merge(state, state)':
election.cpp:21:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |     if(a.tot==-(1e9))return b;if(b.tot==-(1e9))return a;
      |     ^~
election.cpp:21:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |     if(a.tot==-(1e9))return b;if(b.tot==-(1e9))return a;
      |                               ^~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 5 ms 312 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 7 ms 340 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 5 ms 312 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 188 ms 5872 KB Output is correct
7 Correct 168 ms 5812 KB Output is correct
8 Correct 167 ms 5708 KB Output is correct
9 Correct 183 ms 5708 KB Output is correct
10 Correct 188 ms 5704 KB Output is correct
11 Correct 198 ms 5848 KB Output is correct
12 Correct 170 ms 5964 KB Output is correct
13 Correct 171 ms 5796 KB Output is correct
14 Correct 185 ms 5760 KB Output is correct
15 Correct 170 ms 5836 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 5 ms 312 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 188 ms 5872 KB Output is correct
7 Correct 168 ms 5812 KB Output is correct
8 Correct 167 ms 5708 KB Output is correct
9 Correct 183 ms 5708 KB Output is correct
10 Correct 188 ms 5704 KB Output is correct
11 Correct 198 ms 5848 KB Output is correct
12 Correct 170 ms 5964 KB Output is correct
13 Correct 171 ms 5796 KB Output is correct
14 Correct 185 ms 5760 KB Output is correct
15 Correct 170 ms 5836 KB Output is correct
16 Correct 1360 ms 26980 KB Output is correct
17 Correct 1362 ms 26520 KB Output is correct
18 Correct 1347 ms 26988 KB Output is correct
19 Correct 1274 ms 26552 KB Output is correct
20 Correct 1317 ms 26100 KB Output is correct
21 Correct 1432 ms 27796 KB Output is correct
22 Correct 1462 ms 27648 KB Output is correct
23 Correct 1577 ms 27872 KB Output is correct
24 Correct 1595 ms 27624 KB Output is correct
25 Correct 1493 ms 27116 KB Output is correct