oj.uz

Submission #336755

# Submission time Handle Problem Language Result Execution time Memory
336755 2020-12-16T18:09:10 Z CSQ31 Election (BOI18_election) C++14
100 / 100
 864 ms 84976 KB 
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (int)(a.size())
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll A,ll B) {if(!B)return A;return gcd(B,A%B);}
const int MAXN = 555555;
struct node{
	ll sum=0,ans=0,pmx=0,smx = 0;
};
vector<ll>s(MAXN);
node merge(node a,node b){
	node c;
	c.sum = a.sum+b.sum;
	c.pmx = max(a.pmx,a.sum+b.pmx);
	c.smx = max(b.smx,a.smx+b.sum);
	c.ans = max(a.pmx+b.smx,max(a.ans+b.sum,b.ans+a.sum));
	c.ans = max(0LL,c.ans);
	return c;
}
vector<node>t(4*MAXN);
void build(int v,int l,int r){
	if(l == r){
		if(s[l] == 1)t[v] = {1,1,1,1};
		else t[v] = {-1,0,0,0};
		return;
	}
	int mid = (l+r)/2;
	build(2*v,l,mid);
	build(2*v+1,mid+1,r);
	t[v] = merge(t[2*v],t[2*v+1]);
}
node query(int v,int l,int r,int tl,int tr){
	if(l > r){
		return {0,0,0,0};
	}
	if(tl == l && r == tr)return t[v];
	int tm = (tl+tr)/2;
	node a = query(2*v,l,min(tm,r),tl,tm);
	node b = query(2*v+1,max(l,tm+1),r,tm+1,tr);
	return merge(a,b);
}
int main()
{
	owo
	int n,q;
	cin>>n;
	for(int i=1;i<=n;i++){
		char c;cin>>c;
		s[i] = c=='C'?-1:1;
	}
	build(1,1,n);
	//cout<<t[1].ans<<'\n';
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		node ans = query(1,l,r,1,n);
		cout<<ans.ans<<'\n';
	}
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 74220 KB Output is correct
2 Correct 39 ms 74348 KB Output is correct
3 Correct 39 ms 74348 KB Output is correct
4 Correct 39 ms 74348 KB Output is correct
5 Correct 39 ms 74348 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 74220 KB Output is correct
2 Correct 39 ms 74348 KB Output is correct
3 Correct 39 ms 74348 KB Output is correct
4 Correct 39 ms 74348 KB Output is correct
5 Correct 39 ms 74348 KB Output is correct
6 Correct 111 ms 75500 KB Output is correct
7 Correct 105 ms 75500 KB Output is correct
8 Correct 130 ms 75500 KB Output is correct
9 Correct 100 ms 75372 KB Output is correct
10 Correct 112 ms 75372 KB Output is correct
11 Correct 112 ms 75500 KB Output is correct
12 Correct 110 ms 75648 KB Output is correct
13 Correct 113 ms 75628 KB Output is correct
14 Correct 117 ms 75500 KB Output is correct
15 Correct 119 ms 75500 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 74220 KB Output is correct
2 Correct 39 ms 74348 KB Output is correct
3 Correct 39 ms 74348 KB Output is correct
4 Correct 39 ms 74348 KB Output is correct
5 Correct 39 ms 74348 KB Output is correct
6 Correct 111 ms 75500 KB Output is correct
7 Correct 105 ms 75500 KB Output is correct
8 Correct 130 ms 75500 KB Output is correct
9 Correct 100 ms 75372 KB Output is correct
10 Correct 112 ms 75372 KB Output is correct
11 Correct 112 ms 75500 KB Output is correct
12 Correct 110 ms 75648 KB Output is correct
13 Correct 113 ms 75628 KB Output is correct
14 Correct 117 ms 75500 KB Output is correct
15 Correct 119 ms 75500 KB Output is correct
16 Correct 864 ms 84076 KB Output is correct
17 Correct 735 ms 83608 KB Output is correct
18 Correct 777 ms 83820 KB Output is correct
19 Correct 640 ms 83308 KB Output is correct
20 Correct 837 ms 83136 KB Output is correct
21 Correct 836 ms 84844 KB Output is correct
22 Correct 833 ms 84892 KB Output is correct
23 Correct 808 ms 84976 KB Output is correct
24 Correct 823 ms 84760 KB Output is correct
25 Correct 819 ms 84204 KB Output is correct