oj.uz

Submission #347387

# Submission time Handle Problem Language Result Execution time Memory
347387 2021-01-12T18:47:44 Z Sho10 Election (BOI18_election) C++14
100 / 100
 725 ms 48640 KB 
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long 
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define aint(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,q,a[500005];
string s;
struct nodee{
	ll pref;
	ll suf;
	ll sum;
	ll res;
};
nodee tree[10000005];
nodee con(nodee x,nodee y){
nodee ans;
ans.pref=max(x.pref,x.sum+y.pref);
ans.suf=max(y.suf,y.sum+x.suf);
ans.sum=x.sum+y.sum;
ans.res=max(x.pref+y.suf,max(x.sum+y.res,y.sum+x.res));
return ans;
}
void build(ll node,ll l,ll r){
if(l==r){
	tree[node].pref=max(0ll,a[l]);
	tree[node].suf=max(0ll,a[l]);
	tree[node].sum=a[l];
	tree[node].res=max(0ll,a[l]);
	return;
}
ll mid=(l+r)/2;
build(2*node,l,mid);
build(2*node+1,mid+1,r);
tree[node]=con(tree[node*2],tree[node*2+1]);
}
nodee query(ll node,ll l,ll r,ll st,ll dr){
	if(l>dr){
		return {};
	}
	if(r<st){
		return {};
	}
	if(st<=l&&r<=dr){
		return tree[node];
	}
	ll mid=(l+r)/2;
	return con(query(2*node,l,mid,st,dr),query(2*node+1,mid+1,r,st,dr));
}
int32_t main(){
CODE_START;
cin>>n;
cin>>s;
for(ll i=0;i<s.size();i++)
{
	ll s1=0;
	if(s[i]=='C'){
		s1=-1;
	}else s1=+1;
	a[i+1]=s1;
}
build(1,1,n);
cin>>q;
while(q--){
	ll l,r;
	cin>>l>>r;
	cout<<query(1,1,n,l,r).res<<endl;
}
}

Compilation message

election.cpp: In function 'int32_t main()':
election.cpp:68:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 | for(ll i=0;i<s.size();i++)
      |            ~^~~~~~~~~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 70 ms 10476 KB Output is correct
7 Correct 67 ms 10604 KB Output is correct
8 Correct 66 ms 10476 KB Output is correct
9 Correct 59 ms 10476 KB Output is correct
10 Correct 71 ms 10476 KB Output is correct
11 Correct 70 ms 10604 KB Output is correct
12 Correct 69 ms 10604 KB Output is correct
13 Correct 71 ms 10604 KB Output is correct
14 Correct 77 ms 10604 KB Output is correct
15 Correct 73 ms 10476 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 70 ms 10476 KB Output is correct
7 Correct 67 ms 10604 KB Output is correct
8 Correct 66 ms 10476 KB Output is correct
9 Correct 59 ms 10476 KB Output is correct
10 Correct 71 ms 10476 KB Output is correct
11 Correct 70 ms 10604 KB Output is correct
12 Correct 69 ms 10604 KB Output is correct
13 Correct 71 ms 10604 KB Output is correct
14 Correct 77 ms 10604 KB Output is correct
15 Correct 73 ms 10476 KB Output is correct
16 Correct 700 ms 47376 KB Output is correct
17 Correct 610 ms 47104 KB Output is correct
18 Correct 652 ms 47284 KB Output is correct
19 Correct 523 ms 46848 KB Output is correct
20 Correct 725 ms 46592 KB Output is correct
21 Correct 716 ms 48384 KB Output is correct
22 Correct 703 ms 48248 KB Output is correct
23 Correct 704 ms 48640 KB Output is correct
24 Correct 707 ms 48000 KB Output is correct
25 Correct 709 ms 47616 KB Output is correct