oj.uz

Submission #315325

# Submission time Handle Problem Language Result Execution time Memory
315325 2020-10-22T13:33:06 Z nathanlee726 Election (BOI18_election) C++14
100 / 100
 849 ms 40332 KB 
//#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.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 79 ms 8440 KB Output is correct
7 Correct 71 ms 8440 KB Output is correct
8 Correct 73 ms 8440 KB Output is correct
9 Correct 66 ms 8440 KB Output is correct
10 Correct 79 ms 8312 KB Output is correct
11 Correct 80 ms 8568 KB Output is correct
12 Correct 80 ms 8544 KB Output is correct
13 Correct 79 ms 8568 KB Output is correct
14 Correct 84 ms 8568 KB Output is correct
15 Correct 84 ms 8696 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 79 ms 8440 KB Output is correct
7 Correct 71 ms 8440 KB Output is correct
8 Correct 73 ms 8440 KB Output is correct
9 Correct 66 ms 8440 KB Output is correct
10 Correct 79 ms 8312 KB Output is correct
11 Correct 80 ms 8568 KB Output is correct
12 Correct 80 ms 8544 KB Output is correct
13 Correct 79 ms 8568 KB Output is correct
14 Correct 84 ms 8568 KB Output is correct
15 Correct 84 ms 8696 KB Output is correct
16 Correct 827 ms 39308 KB Output is correct
17 Correct 679 ms 38800 KB Output is correct
18 Correct 752 ms 39176 KB Output is correct
19 Correct 613 ms 38672 KB Output is correct
20 Correct 800 ms 38280 KB Output is correct
21 Correct 849 ms 40044 KB Output is correct
22 Correct 834 ms 40076 KB Output is correct
23 Correct 822 ms 40332 KB Output is correct
24 Correct 843 ms 39948 KB Output is correct
25 Correct 820 ms 39504 KB Output is correct