oj.uz

Submission #681796

# Submission time Handle Problem Language Result Execution time Memory
681796 2023-01-14T10:43:41 Z Ronin13 Election (BOI18_election) C++14
100 / 100
 1094 ms 70032 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 5e5 + 1;

struct node{
    ll s, pref;
    node(ll x) : s(x){
        pref = max((ll)0, x);
    }
    node(){
        s = pref = 0;
    }
}t[4 * nmax];

node merg(node a, node b){
    node c;
    c.s = a.s + b.s;
    c.pref = max(a.pref, a.s + b.pref);
    return c;
}

void update(int v, int l, int r, int pos, int val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v] = {val};
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m + 1, r, pos, val);
    t[v] = merg(t[2 * v], t[2 * v + 1]);
}

node get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return {0};
    if(l >= st && r <= fin)
        return t[v];
    int m=  (l + r) / 2;
    node x = get(2 * v, l, m, st, fin);
    node y = get(2 * v + 1, m + 1, r, st, fin);
    return merg(x, y);
}

int main(){
    int n; cin >> n;
    char c[n + 1];
    for(int i = 1; i <= n; i++)
        cin >> c[i];
    for(int i = 1; i <= n; i++){
        if(c[i] == 'C') update(1, 1, n, i, -1);
        else
            update(1, 1, n, i, 1);
    }
    int q; cin >> q;
    vector <int> ans(q);
    vector <pii> qv[n + 1];
    for(int i = 0; i <q; i++){
        int l, r; cin >> l >> r;
        qv[r].pb({l, i});
    }
    vector <int> cur;
    for(int i = 1; i <= n; i++){
        if(c[i] == 'C'){
            if(!cur.empty()){
                int pos = cur.back();
                update(1, 1, n, pos, 1);
                cur.pop_back();
            }
        }
        else{
            cur.pb(i), update(1, 1, n, i, 0);
        }
        for(auto to : qv[i]){
            int l = to.f;
            int x = cur.end() - lower_bound(cur.begin(), cur.end(), l);
            x += get(1, 1, n, l, i).pref;
            ans[to.s] = x;
        }
    }
    for(int i = 0; i < q; i++)
        cout << ans[i] << "\n";
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31708 KB Output is correct
2 Correct 18 ms 31656 KB Output is correct
3 Correct 16 ms 31660 KB Output is correct
4 Correct 16 ms 31700 KB Output is correct
5 Correct 16 ms 31628 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31708 KB Output is correct
2 Correct 18 ms 31656 KB Output is correct
3 Correct 16 ms 31660 KB Output is correct
4 Correct 16 ms 31700 KB Output is correct
5 Correct 16 ms 31628 KB Output is correct
6 Correct 117 ms 36500 KB Output is correct
7 Correct 107 ms 36564 KB Output is correct
8 Correct 114 ms 36360 KB Output is correct
9 Correct 114 ms 36504 KB Output is correct
10 Correct 117 ms 36428 KB Output is correct
11 Correct 119 ms 36688 KB Output is correct
12 Correct 118 ms 36656 KB Output is correct
13 Correct 120 ms 36820 KB Output is correct
14 Correct 119 ms 36676 KB Output is correct
15 Correct 113 ms 36556 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31708 KB Output is correct
2 Correct 18 ms 31656 KB Output is correct
3 Correct 16 ms 31660 KB Output is correct
4 Correct 16 ms 31700 KB Output is correct
5 Correct 16 ms 31628 KB Output is correct
6 Correct 117 ms 36500 KB Output is correct
7 Correct 107 ms 36564 KB Output is correct
8 Correct 114 ms 36360 KB Output is correct
9 Correct 114 ms 36504 KB Output is correct
10 Correct 117 ms 36428 KB Output is correct
11 Correct 119 ms 36688 KB Output is correct
12 Correct 118 ms 36656 KB Output is correct
13 Correct 120 ms 36820 KB Output is correct
14 Correct 119 ms 36676 KB Output is correct
15 Correct 113 ms 36556 KB Output is correct
16 Correct 1018 ms 68264 KB Output is correct
17 Correct 884 ms 67804 KB Output is correct
18 Correct 859 ms 66884 KB Output is correct
19 Correct 953 ms 67696 KB Output is correct
20 Correct 1094 ms 67332 KB Output is correct
21 Correct 1080 ms 69764 KB Output is correct
22 Correct 904 ms 69224 KB Output is correct
23 Correct 919 ms 70032 KB Output is correct
24 Correct 867 ms 69412 KB Output is correct
25 Correct 825 ms 68440 KB Output is correct