Submission #865451

#TimeUsernameProblemLanguageResultExecution timeMemory
865451ALeonidouElection (BOI18_election)C++17
0 / 100
1 ms856 KiB
#include <iostream> #include <vector> #include <stack> #include <queue> #include <map> #include <set> #include <algorithm> #include <iomanip> #include <cmath> #include <bitset> #include <string> #include <fstream> #include <cstring> using namespace std; #define ll long long #define llu unsigned long long #define ld long double #define F first #define S second #define endl "\n" #define MID ((l+r)/2) #define sorv(a) sort(a.begin(),a.end()) #define revv(a) reverse(a.begin(),a.end()) #define all(x) (x).begin(),(x).end() #define sz(x) (ll)(x).size() #define ins insert #define pb push_back #define inf 1e9 #define INF 1e18 #define MOD 1000000007 #define MOD2 998244353 typedef pair <ll, ll> ii; typedef pair <ll,ii> iii; typedef vector <ll> vi; typedef vector <ii> vii; typedef vector <iii> viii; typedef set <ll> si; typedef map <ll,ll> mi; #ifndef ONLINE_JUDGE #define ONLINE_JUDGE #endif #ifndef ONLINE_JUDGE template<typename T>void printArr(T *arr,ll l,ll m=0){if(m==1){for(ll i=0;i<l;i++)cout<<arr[i]<<" ";cout<<endl;}else{cout<<endl;for(ll i=0;i<l;i++)cout<<i<<": "<<arr[i]<<endl;}} #define printArr2D(arr,n,m)cout<<endl;for(ll i=0;i<n;i++){for(ll j=0;j<m;j++)cout<<arr[i][j]<<" ";cout<<endl;}cout<<endl; template<typename T>void printVct(vector<T> v,ll m=0){if(m==1){for(ll i=0;i<sz(v);i++)cout<<v[i]<<" ";cout<<endl;}else{cout<<endl;for(ll i=0; i<sz(v);i++)cout<<i<<": "<<v[i]<<endl;}} template<typename T>void printVct2D(vector<vector<T> >v){cout<<endl;for(ll i=0;i<sz(v);i++){cout<<i<<": ";for(ll j=0;j<sz(v[i]);j++)cout<<v[i][j]<<" ";cout<<endl;}} template<typename T>void printVctPair(vector<T> v,ll m=0){if(m==1){for(ll i=0;i<sz(v);i++)cout<<v[i].F<<":"<<v[i].S<<" ";cout<<endl;}else{cout<<endl;for(ll i=0;i<sz(v);i++)cout<<i<<": "<<v[i].F<<" : "<<v[i].S<<endl;}} template<typename T>void printVctPair2D(vector<vector<T> >v){cout<<endl;for(ll i=0;i<sz(v);i++){cout<<i<<": ";for(ll j=0;j<sz(v[i]);j++)cout<<v[i][j].F<<":"<<v[i][j].S<<" ";cout<<endl;}} template<typename T>void printVctPair3(vector<T> v,ll m=0){cout<<endl;for(ll i=0;i<sz(v);i++)cout<<i<<": ("<<v[i].F<<" : "<<v[i].S.F<<" : "<<v[i].S.S<<")"<<endl;} template<typename T1,typename T2>void printMap(map<T1,T2>mp){cout<<endl;for(typename map<T1,T2>::iterator it=mp.begin();it!=mp.end();it++)cout<<it->F<<" -> "<<it->S<<endl;} template<typename T>void printSet(set<T>st,ll m=0){typename set<T>::iterator it;if(m){for(it=st.begin();it!=st.end();it++)cout<<*it<<" ";cout<<endl;}else{cout<<endl;for(it=st.begin();it!=st.end();it++)cout<<*it<<endl;}} void check(ll n){cout<<"CHECKPOINT "<<n<<"\n\n";} #define dbg(x) cout<<#x<<":"<<x<<endl #define dbg2(x,y) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl #define dbg3(x,y,z) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl #define dbg4(x,y,z,w) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<" "<<#w<<":"<<w<<endl #define dbg5(x,y,z,w,v) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<" "<<#w<<":"<<w<<" "<<#v<<":"<<v<<endl #define dbg6(x,y,z,w,v,u) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<" "<<#w<<":"<<w<<" "<<#v<<":"<<v<<" "<<#u<<":"<<u<<endl #define dbgp(x) cout<<#x<<":("<<x.F<<" "<<x.S<<")"<<endl #define dbgp2(x,y) cout<<#x<<":("<<x.F<<","<<x.S<<") "<<#y<<":("<<y.F<<","<<y.S<<")"<<endl #define dbgt(x) cout<<#x<<":("<<x.F<<" "<<x.S.F<<" "<<x.S.S<<")"<<endl #define dbgt2(x,y) cout<<#x<<":("<<x.F<<" "<<x.S.F<<" "<<x.S.S<<") "<<#y<<":("<<y.F<<" "<<y.S.F<<" "<<y.S.S<<")"<<endl #else template<typename T>void printArr(T *arr,ll l,ll m=0){} #define printArr2D(arr,n,m) template<typename T>void printVct(vector<T> v,ll m=0){} template<typename T>void printVct2D(vector<vector<T> >v){} template<typename T>void printVctPair(vector<T> v,ll m=0){} template<typename T>void printVctPair2D(vector<vector<T> >v){} template<typename T>void printVctPair3(vector<T> v,ll m=0){} template<typename T1,typename T2>void printMap(map<T1,T2>mp){} template<typename T>void printSet(set<T>st,ll m=0){} void check(ll n){} #define dbg(x) #define dbg2(x,y) #define dbg3(x,y,z) #define dbg4(x,y,z,w) #define dbg5(x,y,z,w,v) #define dbg6(x,y,z,w,v,u) #define dbgp(x) #define dbgp2(x,y) #define dbgt(x) #define dbgt2(x,y) #endif const ll dx[8]={1,-1,0,0,1,1,-1,-1}, dy[8]={0,0,1,-1,1,-1,1,-1}; ll charToIntNum(char c){return (ll)c-48;} char intToCharNum(ll n){return (char)n+48;} ll charToIntLower(char c){return (ll)c-97;} char intToCharLower(ll n){return (char)n+97;} ll charToIntUpper(char c){return (ll)c-65;} char intToCharUpper(ll n){return (char)n+65;} void tabb(ll n){for(ll i=0;i<n;i++)cout<<"\t";} ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);} void yesno(bool a){if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}} #define N 500000 ll arr[N+1]; ll n; //minimum seg tree struct node{ ll val, rval; node *L, *R; void build(vi &s, ll l = 0, ll r =n-1){ if (l == r){ val = s[l]; } else{ L = new node, R = new node; L->build(s,l, MID), R-> build(s,MID+1,r); val = min(L->val,R->val); } } ll query(ll tl, ll tr, ll l = 0, ll r = n-1){ if (tl >= l && tr <= r){ return val; } else if(tr < l || r < tl){ return INF; } else{ return min(L->query(tl,tr,l,MID), R->query(tl,tr,MID+1,r)); } } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; string tmp; cin>>tmp; for (ll i =0; i<n; i++){ if (tmp[i] == 'T') arr[i] = -1; else arr[i] = 1; } vi s(n), sr(n); s[0] = arr[0]; for (ll i =1; i<n; i++) s[i] = s[i-1] + arr[i]; sr[n-1] = arr[n-1]; for (ll i =n-2; i>=0; i--) sr[i] = sr[i+1] + arr[i]; printArr(arr,n,1); printVct(s,1); printVct(sr,1); node root_s, root_sr; root_s.build(s), root_sr.build(sr); ll q; cin>>q; ll l,r,sum; while (q--){ cin>>l>>r; l--, r--; ll s_before, sr_before; if (l == 0) s_before = 0; else s_before = s[l-1]; if (r == n-1) sr_before = 0; else sr_before = sr[r+1]; dbg2(s_before, sr_before); ll qs = root_s.query(l,r); ll qsr = root_sr.query(l,r); dbg2(qs,qsr); ll ans1 = (qs - s_before) * (-1); ll ans2 = (qsr - sr_before) * (-1); dbg2(ans1, ans2); ll ans = max(ans1, ans2); if (ans < 0) ans= 0; cout<<ans<<endl; } return 0; } /* 11 CCCTTTTTTCC 1 1 11 11 CCCTTTTTTCC 1 4 9 11 CCCTTTTTTCC 3 1 11 4 9 1 6 01210-*-*-*&%&*&%$ -CCTTTTCTCTTTCCTTT -----^.........^-- -12345678901234567 |010-*&%&*-010 | |-012343210-0 |TCCCCCTTTTTC |-^.......^-- |12345678901234567 -*-*&* TTCTTC */

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:170:9: warning: unused variable 'sum' [-Wunused-variable]
  170 |  ll l,r,sum;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...