제출 #315325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
315325		nathanlee726	Election (BOI18_election)	C++14	100 / 100	849 ms	40332 KiB

election

//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
struct NODE{
	int v,ma,mi;
}seg[2000000];
int pre[500010];
void build(int p,int l,int r){
	if(l==r){
		seg[p].v=0;
		seg[p].mi=seg[p].ma=pre[l];
		return;
	}
	int m=(l+r)/2;
	build(p*2,l,m);
	build(p*2+1,m+1,r);
	seg[p].v=max(seg[p*2].v,max(seg[p*2+1].v,seg[p*2+1].ma-seg[p*2].mi));
	seg[p].ma=max(seg[p*2].ma,seg[p*2+1].ma);
	seg[p].mi=min(seg[p*2].mi,seg[p*2+1].mi);
	return;
}
pair<int,pii> qry(int p,int l,int r,int ql,int qr){
	if(l>qr||r<ql)return{0,{-1e9,1e9}};
	if(l>=ql&&r<=qr)return {seg[p].v,{seg[p].ma,seg[p].mi}};
	int m=(l+r)/2;
	pair<int,pii> t1=qry(p*2,l,m,ql,qr),t2=qry(p*2+1,m+1,r,ql,qr);
	t1.X=max(max(t1.X,t2.X),t2.Y.X-t1.Y.Y);
	t1.Y.X=max(t1.Y.X,t2.Y.X);
	t1.Y.Y=min(t1.Y.Y,t2.Y.Y);
	return t1;
}
signed main(){
	IOS();
	int n,q;
	cin>>n;
	string s;
	cin>>s;
	cin>>q;
	pre[0]=0;
	F(n){
		pre[i+1]=pre[i]+(s[i]=='C'?1:-1);
		//cout<<pre[i+1]<<endl;
	}
	build(1,0,n);
	F(q){
		int l,r;
		cin>>l>>r;
		auto pt=qry(1,0,n,l-1,r);
		//cout<<pt.X<<" "<<pt.Y.X<<" "<<pt.Y.Y<<endl;
		int s=max(0ll,-(pt.Y.Y-pre[l-1]));
		s+=(max(0ll,-(pre[r]-pre[l-1]+s-pt.X)));
		cout<<s<<endl;
	}
return 0;
}

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18