Submission #61836

#TimeUsernameProblemLanguageResultExecution timeMemory
61836BenqElection (BOI18_election)C++11
100 / 100
1969 ms42608 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 1<<19; template<class T, int SZ> struct BIT { T bit[SZ+1]; BIT() { memset(bit,0,sizeof bit); } void upd(int k, T val) { // add val to index k for( ;k <= SZ; k += (k&-k)) bit[k] += val; } T query(int k) { T temp = 0; for (;k > 0;k -= (k&-k)) temp += bit[k]; return temp; } T query(int l, int r) { return query(r)-query(l-1); } // range query [l,r] }; BIT<int,MX> B; template<class T, int SZ> struct LazySegTree { T mx[2*SZ], lazy[2*SZ]; // set SZ to a power of 2 LazySegTree() { memset (mx,0,sizeof mx); memset (lazy,0,sizeof lazy); } void push(int ind, int L, int R) { mx[ind] += lazy[ind]; if (L != R) lazy[2*ind] += lazy[ind], lazy[2*ind+1] += lazy[ind]; lazy[ind] = 0; } void pull(int ind) { mx[ind] = max(mx[2*ind],mx[2*ind+1]); } void build() { F0Rd(i,SZ) pull(i); } T query(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) { push(ind,L,R); if (lo > R || L > hi) return -MOD; if (lo <= L && R <= hi) return mx[ind]; int M = (L+R)/2; return max(query(lo,hi,2*ind,L,M), query(lo,hi,2*ind+1,M+1,R)); } void upd(int lo, int hi, ll inc, int ind = 1, int L = 0, int R = SZ-1) { push(ind,L,R); if (hi < L || R < lo) return; if (lo <= L && R <= hi) { lazy[ind] = inc; push(ind,L,R); return; } int M = (L+R)/2; upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R); pull(ind); } }; LazySegTree<int,MX> L; int N,Q,cum[MX], ans[MX]; string S; vpi q[MX]; vpi v; void rem() { B.upd(v.back().s,-1); L.upd(v.back().s,MX-1,-1); v.pop_back(); } void ad(int x) { B.upd(x,1); L.upd(x,MX-1,1); v.pb({cum[x],x}); } void solve(int x) { while (sz(v) && v.back().f >= cum[x]) rem(); for (auto z: q[x]) { /*cout << z.s << " " << B.query(x+1,z.f) << " " << L.query(x,z.f) << " " << L.query(z.f,z.f)<< "\n"; cout << z.f << "\n"; for (auto a: v) cout << a.f << ' ' << a.s << " | "; cout << "\n"; cout << L.query(x+1,x+1) << " " << L.query(x+2,x+2) << " " << L.query(x+3,x+3) << "\n";*/ ans[z.s] = B.query(x+1,z.f)+L.query(x,z.f)-L.query(z.f,z.f); } if (x) ad(x); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> S >> Q; F0R(i,N) cum[i+1] = cum[i] + (S[i] == 'C' ? 1 : -1); F0R(i,N+1) L.upd(i,i,cum[i]); F0R(i,Q) { int L,R; cin >> L >> R; q[L-1].pb({R,i}); } F0Rd(i,N+1) solve(i); F0R(i,Q) cout << ans[i] << "\n"; } /* Look for: * the exact constraints (multiple sets are too slow for n=10^6 :( ) * special cases (n=1?) * overflow (ll vs int?) * array bounds */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...