Submission #439878

#	Time	Username	Problem	Language	Result	Execution time	Memory
439878		RohamIzadidoost	Election (BOI18_election)	C++14	0 / 100	2 ms	460 KiB

election

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ld long double
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 5000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
int n , q , ps[maxn] , fen[maxn] , sp[maxn]  , res;
pii seg[4  * maxn]  , ges[4 * maxn] ;  
string s ; 
void add(int i){
	for(i ++ ; i < maxn ; i += i & -i){
		fen[i] ++ ; 
	}
}
int get(int i){
	res = 0 ; 
	for(i ++ ; i ; i &= i-1 ) res += fen[i]  ; 
	return res ; 
}
int GET(int l , int r){
	return get(r) - get(l-1) ; 
}
void bld(int x = 1 , int lx = 1 , int rx = n + 1){
	if(rx - lx == 1){
		ges[x] = {sp[lx] , lx }; 
		return ; 
	}
	int mid = lx + rx >> 1 ; 
	bld(x << 1 , lx , mid) ; 
	bld(x << 1 | 1, mid , rx) ; 
	ges[x] = min(ges[x << 1] , ges[x << 1 | 1]) ; 
}
pii getmn(int l , int r, int x = 1 , int lx = 1 , int rx = n + 1){
	if(lx >= r || rx <= l ) return {mod , mod} ; 
	if(lx >= l && rx <= r){
		return ges[x] ; 
	}
	int mid = lx + rx >> 1 ; 
	return min(getmn(l , r , x << 1  , lx , mid) , getmn(l , r , x << 1 | 1 , mid , rx)) ; 
}
void build(int x = 1,  int lx = 1, int rx = n + 1){
	if(rx - lx == 1){
		seg[x] = {ps[lx] , -lx }; 
		return ; 
	}
	int mid = lx + rx >> 1 ; 
	build(x << 1 , lx , mid) ; 
	build(x << 1 | 1 , mid , rx) ; 
	seg[x] = min(seg[x << 1] , seg[x << 1 | 1]) ; 
}
pii getmin(int l , int r , int x = 1 , int lx = 1 , int rx = n + 1){
	if(lx >= r || rx <= l){
		return {mod , mod} ; 
	}
	if(lx >= l && rx <= r){
		return seg[x] ; 
	}
	int mid = lx + rx >> 1 ; 
	return min(getmin(l  , r , x << 1  , lx , mid) , getmin(l , r, x << 1 | 1 , mid , rx)) ;  
} 
int main()
{
	migmig ;
	cin>>n>>s ; 
	s = '&'+s ; 
	for(int i = 1 ; i <= n ; i ++ ){
		ps[i] = ps[i-1] + (s[i] == 'C' ? 1 : -1) ; 
		if(s[i] == 'T'){
			add(i) ; 	
		}
	}
	for(int i = n ; i >= 1 ; i-- ){
		sp[i] = sp[i + 1] + (s[i] == 'C' ? 1 : -1) ; 
	}
	cin>>q ; 
	int l , r , p1 , p2 , val ;
	pii res1 , res2 ;  
	build() ; 
	bld() ;
	while(q--){
		cin>>l>>r ; 
		res1 = getmin(l , r + 1 ) ; 
		res2 = getmn(l , r + 1) ;
		p1 = -1 * res1.Y ; 
		p2 = res2.Y  ; 
		if(p1 >= p2){
			val = GET(p2 , p1) ; 
			val = min(val , max( (ps[p1] - ps[l-1]) * -1 , (sp[p2] - sp[r + 1]) * -1 )) ; 
		}else{
			val = 0 ; 
		}
//		cout<<"p1 :" << p1 << " p2 :" << p2 <<" val :" << val << endl ; 
		cout<<val + max(0 , (ps[p1] - ps[l-1]) * -1 - val) + max(0 , (sp[p2] - sp[r + 1]) * -1 - val) << "\n" ;  
	}
}

Compilation message (stderr)

election.cpp: In function 'void bld(int, int, int)':
election.cpp:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int mid = lx + rx >> 1 ;
      |            ~~~^~~~
election.cpp: In function 'std::pair<int, int> getmn(int, int, int, int, int)':
election.cpp:56:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |  int mid = lx + rx >> 1 ;
      |            ~~~^~~~
election.cpp: In function 'void build(int, int, int)':
election.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid = lx + rx >> 1 ;
      |            ~~~^~~~
election.cpp: In function 'std::pair<int, int> getmin(int, int, int, int, int)':
election.cpp:76:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |  int mid = lx + rx >> 1 ;
      |            ~~~^~~~

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