Submission #439874

#TimeUsernameProblemLanguageResultExecution timeMemory
439874RohamIzadidoostElection (BOI18_election)C++14
0 / 100
3 ms460 KiB
#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 = res1.Y ; p2 = -1 * 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 ;
      |            ~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...