oj.uz

Submission #61836

# Submission time Handle Problem Language Result Execution time Memory
61836 2018-07-26T19:42:52 Z Benq Election (BOI18_election) C++11
100 / 100
 1969 ms 42608 KB 
#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
*/

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23036 KB Output is correct
2 Correct 28 ms 23144 KB Output is correct
3 Correct 27 ms 23216 KB Output is correct
4 Correct 29 ms 23216 KB Output is correct
5 Correct 25 ms 23332 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23036 KB Output is correct
2 Correct 28 ms 23144 KB Output is correct
3 Correct 27 ms 23216 KB Output is correct
4 Correct 29 ms 23216 KB Output is correct
5 Correct 25 ms 23332 KB Output is correct
6 Correct 206 ms 25700 KB Output is correct
7 Correct 207 ms 25700 KB Output is correct
8 Correct 194 ms 25700 KB Output is correct
9 Correct 220 ms 25700 KB Output is correct
10 Correct 281 ms 25700 KB Output is correct
11 Correct 211 ms 25872 KB Output is correct
12 Correct 246 ms 25872 KB Output is correct
13 Correct 255 ms 26080 KB Output is correct
14 Correct 225 ms 26080 KB Output is correct
15 Correct 213 ms 26080 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23036 KB Output is correct
2 Correct 28 ms 23144 KB Output is correct
3 Correct 27 ms 23216 KB Output is correct
4 Correct 29 ms 23216 KB Output is correct
5 Correct 25 ms 23332 KB Output is correct
6 Correct 206 ms 25700 KB Output is correct
7 Correct 207 ms 25700 KB Output is correct
8 Correct 194 ms 25700 KB Output is correct
9 Correct 220 ms 25700 KB Output is correct
10 Correct 281 ms 25700 KB Output is correct
11 Correct 211 ms 25872 KB Output is correct
12 Correct 246 ms 25872 KB Output is correct
13 Correct 255 ms 26080 KB Output is correct
14 Correct 225 ms 26080 KB Output is correct
15 Correct 213 ms 26080 KB Output is correct
16 Correct 1778 ms 40228 KB Output is correct
17 Correct 1396 ms 40228 KB Output is correct
18 Correct 1659 ms 40228 KB Output is correct
19 Correct 1446 ms 40228 KB Output is correct
20 Correct 1680 ms 40228 KB Output is correct
21 Correct 1721 ms 42236 KB Output is correct
22 Correct 1626 ms 42236 KB Output is correct
23 Correct 1923 ms 42608 KB Output is correct
24 Correct 1969 ms 42608 KB Output is correct
25 Correct 1707 ms 42608 KB Output is correct