oj.uz

Submission #861441

# Submission time Handle Problem Language Result Execution time Memory
861441 2023-10-16T07:55:38 Z ReLice Election (BOI18_election) C++14
100 / 100
 450 ms 78108 KB 
#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bc back()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18+7;
const ll mod=998244353;
const ll N=5e5+7;
const ld eps=1e-9;
struct node{
	ll pref,suf,ans,sum;
	node operator +(node a){
		node b;
		b.sum=a.sum+sum;
		b.pref=max(pref,a.pref+sum);
		b.suf=max(a.suf,suf+a.sum);
		b.ans=max({0ll,sum+a.ans,a.sum+ans,pref+a.suf});
		return b;
	}
};
ll a[N];
vector <node> t(N*4);
void build(ll v,ll tl,ll tr){
	if(tl==tr){
		t[v].sum=a[tl];
		t[v].ans=t[v].pref=t[v].suf=max(a[tl],0ll);
		
		return;
	}
	ll tm=(tl+tr)/2;
	build(v*2,tl,tm);
	build(v*2+1,tm+1,tr);
	t[v]=t[v*2]+t[v*2+1];
}
node go(ll v,ll tl,ll tr,ll l,ll r){
	if(tl>r || tr<l)return {0ll,0ll,0ll,0ll};
	if(l<=tl && tr<=r){
		return t[v];
	}
	ll tm=(tl+tr)/2;
	node a=go(v*2,tl,tm,l,r),b=go(v*2+1,tm+1,tr,l,r);
	return a+b;
}
void solve(){
    ll i,q;
    ll n;
	cin>>n;
	str s;
	cin>>s;
	s=" "+s;
	for(i=1;i<=n;i++){
		if(s[i]=='C') a[i]=-1;
		else a[i]=1;
	}
	build(1,1,n);
	cin>>q;
	ll l,r;
	for(i=0;i<q;i++){
		cin>>l>>r;
		cout<<go(1,1,n,l,r).ans<<endl;
	}
}

signed main(){
    start();
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll t=1;
    //cin>>t;
    while(t--) solve();
}
/*
100
1 50 69 33  544
2 18 71 14 25 91 45
 
 
 
*/

Compilation message

election.cpp: In function 'void fre(std::string)':
election.cpp:24:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:24:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 63064 KB Output is correct
2 Correct 10 ms 63068 KB Output is correct
3 Correct 10 ms 63064 KB Output is correct
4 Correct 10 ms 63068 KB Output is correct
5 Correct 10 ms 63068 KB Output is correct
6 Correct 50 ms 65696 KB Output is correct
7 Correct 51 ms 65624 KB Output is correct
8 Correct 50 ms 65616 KB Output is correct
9 Correct 57 ms 65528 KB Output is correct
10 Correct 50 ms 65636 KB Output is correct
11 Correct 49 ms 65624 KB Output is correct
12 Correct 55 ms 65724 KB Output is correct
13 Correct 59 ms 65928 KB Output is correct
14 Correct 53 ms 65620 KB Output is correct
15 Correct 50 ms 65864 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 63064 KB Output is correct
2 Correct 10 ms 63068 KB Output is correct
3 Correct 10 ms 63064 KB Output is correct
4 Correct 10 ms 63068 KB Output is correct
5 Correct 10 ms 63068 KB Output is correct
6 Correct 50 ms 65696 KB Output is correct
7 Correct 51 ms 65624 KB Output is correct
8 Correct 50 ms 65616 KB Output is correct
9 Correct 57 ms 65528 KB Output is correct
10 Correct 50 ms 65636 KB Output is correct
11 Correct 49 ms 65624 KB Output is correct
12 Correct 55 ms 65724 KB Output is correct
13 Correct 59 ms 65928 KB Output is correct
14 Correct 53 ms 65620 KB Output is correct
15 Correct 50 ms 65864 KB Output is correct
16 Correct 447 ms 76424 KB Output is correct
17 Correct 357 ms 76788 KB Output is correct
18 Correct 406 ms 76996 KB Output is correct
19 Correct 330 ms 76432 KB Output is correct
20 Correct 450 ms 76288 KB Output is correct
21 Correct 437 ms 78080 KB Output is correct
22 Correct 434 ms 77820 KB Output is correct
23 Correct 437 ms 78072 KB Output is correct
24 Correct 438 ms 78108 KB Output is correct
25 Correct 433 ms 77160 KB Output is correct