oj.uz

Submission #384571

# Submission time Handle Problem Language Result Execution time Memory
384571 2021-04-01T20:57:48 Z Peti Election (BOI18_election) C++14
100 / 100
 1698 ms 97360 KB 
#include <bits/stdc++.h>

using namespace std;

struct segment_tree{
    vector<int> st, stmin, stadd;
    int maxn = 0;

    void init(int n){
        maxn = n;
        st.assign(4*n, 0);
        stmin.assign(4*n, 0);
        stadd.assign(4*n, 0);
        return;
    }

    void pont_upd(int x, int l, int r){
        if(l+1 == r){
            st[x] = stmin[x] = stadd[x];
            return;
        }
        st[x] = st[2*x+1] + st[2*x+2] + stadd[x] * (r-l);
        stmin[x] = min(stmin[2*x+1], stmin[2*x+2]) + stadd[x];
        return;
    }

    void add(int L, int R, int c, int x, int l, int r){
        if(r <= L || R <= l)
            return;
        if(L <= l && r <= R){
            stadd[x] += c;
            pont_upd(x, l, r);
            return;
        }
        int m = (l+r)/2;
        add(L, R, c, 2*x+1, l, m);
        add(L, R, c, 2*x+2, m, r);
        pont_upd(x, l, r);
        return;
    }

    void add(int l, int r, int c){
        add(l, r, c, 0, 0, maxn);
        return;
    }

    int minert(int L, int R, int x, int l, int r){
        if(r <= L || R <= l)
            return (int)1e9;
        if(L <= l && r <= R)
            return stmin[x];
        int m = (l+r)/2;
        return min(minert(L, R, 2*x+1, l, m), minert(L, R, 2*x+2, m, r)) + stadd[x];
    }

    int minert(int l, int r) {return minert(l, r, 0, 0, maxn); }

    int ossz(int L, int R, int c, int x, int l, int r){
        if(r <= L || R <= l)
            return 0;
        if(L <= l && r <= R)
            return st[x] + c*(r-l);
        int m = (l+r)/2;
        return ossz(L, R, c + stadd[x], 2*x+1, l, m)+ossz(L, R, c + stadd[x], 2*x+2, m, r);
    }

    int ossz(int l, int r) {return ossz(l, r, 0, 0, 0, maxn); }
};

int main()
{
    cin.sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    string s;
    cin>>n;
    cin>>s;
    cin>>q;

    vector<int> ki(q);
    vector<vector<pair<int, int>>> v(n);

    for(int i = 0; i < q; i++){
        int l, r;
        cin>>l>>r;
        v[l-1].push_back(make_pair(r-1, i));
    }

    segment_tree st, st2;
    st.init(n+1);
    st2.init(n+1);

    set<int> inds;
    for(int i = 0; i < n; i++){
        if(s[i] == 'T'){
            inds.insert(i);
            st2.add(i, i+1, 1);
        }
    }

    for(int i = n-1; i >= 0; i--){
        if(s[i] == 'C'){
            auto it = inds.lower_bound(i);
            if(it != inds.end()){
                st2.add((*it), (*it)+1, -1);
                st.add(0, (*it)+1, -1);
                inds.erase(it);
            }
            st.add(0, i+1, 1);
        }
        for(pair<int, int> temp : v[i])
            ki[temp.second] = st2.ossz(i, temp.first+1) + st.minert(temp.first+1, temp.first+2) - st.minert(i, temp.first+2);
    }

    for(int x : ki)
        cout<<x<<"\n";

    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 748 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 4 ms 748 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 4 ms 748 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 748 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 4 ms 748 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 4 ms 748 KB Output is correct
6 Correct 188 ms 13348 KB Output is correct
7 Correct 158 ms 12652 KB Output is correct
8 Correct 165 ms 12780 KB Output is correct
9 Correct 166 ms 13164 KB Output is correct
10 Correct 169 ms 12780 KB Output is correct
11 Correct 175 ms 13676 KB Output is correct
12 Correct 173 ms 13420 KB Output is correct
13 Correct 165 ms 13932 KB Output is correct
14 Correct 168 ms 13164 KB Output is correct
15 Correct 165 ms 12804 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 748 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 4 ms 748 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 4 ms 748 KB Output is correct
6 Correct 188 ms 13348 KB Output is correct
7 Correct 158 ms 12652 KB Output is correct
8 Correct 165 ms 12780 KB Output is correct
9 Correct 166 ms 13164 KB Output is correct
10 Correct 169 ms 12780 KB Output is correct
11 Correct 175 ms 13676 KB Output is correct
12 Correct 173 ms 13420 KB Output is correct
13 Correct 165 ms 13932 KB Output is correct
14 Correct 168 ms 13164 KB Output is correct
15 Correct 165 ms 12804 KB Output is correct
16 Correct 1698 ms 93664 KB Output is correct
17 Correct 1425 ms 89084 KB Output is correct
18 Correct 1648 ms 90604 KB Output is correct
19 Correct 1468 ms 92248 KB Output is correct
20 Correct 1612 ms 90316 KB Output is correct
21 Correct 1644 ms 96896 KB Output is correct
22 Correct 1680 ms 93184 KB Output is correct
23 Correct 1641 ms 97360 KB Output is correct
24 Correct 1652 ms 92968 KB Output is correct
25 Correct 1529 ms 87680 KB Output is correct