oj.uz

Submission #380822

# Submission time Handle Problem Language Result Execution time Memory
380822 2021-03-23T07:12:01 Z jainbot27 Election (BOI18_election) C++17
100 / 100
 513 ms 45056 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

struct Tree {
    typedef pii T;
    T Unit = {0, 0};
    T f(T a, T b) { return {a.f+b.f, max(a.s, a.f+b.s)}; } // (any associative fn)
    vector<T> s; int n;
    Tree(int n = 0) : s(2*n, Unit), n(n) {}
    void update(int pos, T val) {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e) { // query [b, e)
        T ra = Unit, rb = Unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

typedef int node;
struct BIT{
    //ask for queries 0 idxed or remove ++idx/++r
    vector<node> bit;
    int n;
    void init(int x){
        n=x+1;
        bit.assign(n + 1,0);
    }
    node sum(int r){
        node ret = 0;
        for(r++; r ; r -= r & -r){
            ret += bit[r];
        }
        return ret;
    }
    node sum(int l, int r){
        return sum(r) - sum(l-1);
    }
    void add(int idx, node delta){
        for(idx++; idx < n; idx += idx & -idx){
            bit[idx] += delta;
        }
    }
}bit;

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; string s;
    cin >> n; cin >> s;
    int q; cin >> q;
    vector<vpii> qq(n);
    F0R(i, q){
        int l, r;
        cin >> l >> r;
        l--; r--; 
        qq[r].pb({l, i});
    }
    Tree seg(n);
    bit.init(n);
    stack<int> vals;
    vi ans(q);
    F0R(i, n){
        if(s[i]=='C'){
            seg.update(i, pii{-1, 0});
            if(!vals.empty()){
                int T = vals.top(); vals.pop();
                seg.update(T, {1, 1});
                bit.add(T, -1);
                //cout << "WE GOT HERE" << endl;
            }
        }
        else{
            vals.push(i);
            bit.add(i, 1);
        }
        trav(v, qq[i]){
            int r = bit.sum(v.f, i);
            //cout << bit.sum(i, v.f) << ' ' << seg.query(i, v.f+1).s << nl;
            r += seg.query(v.f, i+1).s;
            ans[v.s] = r;
        }
    }
    trav(x, ans) cout << x << nl;

    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 512 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 51 ms 6272 KB Output is correct
7 Correct 45 ms 5868 KB Output is correct
8 Correct 51 ms 5996 KB Output is correct
9 Correct 50 ms 6252 KB Output is correct
10 Correct 50 ms 6124 KB Output is correct
11 Correct 48 ms 6380 KB Output is correct
12 Correct 54 ms 6380 KB Output is correct
13 Correct 52 ms 6380 KB Output is correct
14 Correct 49 ms 6380 KB Output is correct
15 Correct 49 ms 6252 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 51 ms 6272 KB Output is correct
7 Correct 45 ms 5868 KB Output is correct
8 Correct 51 ms 5996 KB Output is correct
9 Correct 50 ms 6252 KB Output is correct
10 Correct 50 ms 6124 KB Output is correct
11 Correct 48 ms 6380 KB Output is correct
12 Correct 54 ms 6380 KB Output is correct
13 Correct 52 ms 6380 KB Output is correct
14 Correct 49 ms 6380 KB Output is correct
15 Correct 49 ms 6252 KB Output is correct
16 Correct 513 ms 43392 KB Output is correct
17 Correct 382 ms 40576 KB Output is correct
18 Correct 438 ms 41856 KB Output is correct
19 Correct 417 ms 43136 KB Output is correct
20 Correct 499 ms 42368 KB Output is correct
21 Correct 504 ms 44600 KB Output is correct
22 Correct 505 ms 44288 KB Output is correct
23 Correct 499 ms 45056 KB Output is correct
24 Correct 510 ms 44476 KB Output is correct
25 Correct 506 ms 43776 KB Output is correct