oj.uz

Submission #108919

# Submission time Handle Problem Language Result Execution time Memory
108919 2019-05-02T17:20:43 Z win11905 Election (BOI18_election) C++11
100 / 100
 2008 ms 44312 KB 
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author win11905
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define iii tuple<int, int, int>
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

const int N = 1<<19;

class election {
private:
    int n, m;
    int ans[N];
    char arr[N];
    vector<pii> que[N];
    int t[N<<1], lz[N<<1];
    void push(int p) {
        if(!lz[p]) return;
        t[p] += lz[p];
        if(p < N) lz[p<<1] += lz[p], lz[p<<1|1] += lz[p];
        lz[p] = 0;
    }
    template<typename T>
    void travel(int x, int y, const T &f, int p = 1, int l = 0, int r = N-1) {
        push(p);
        if(x > r || l > y || x > y) return;
        if(x <= l && r <= y) return f(p);
        int m = l + r >> 1;
        travel(x, y, f, p<<1, l, m), travel(x, y, f, p<<1|1, m+1, r);
        t[p] = min(t[p<<1], t[p<<1|1]);
    }
public:
    void solve(istream& cin, ostream& cout) {
        cin >> n;
        cin >> arr+1;
        cin >> m;
        for(int i = 0, l, r; i < m; ++i) {
            cin >> l >> r;
            que[r].emplace_back(l, i);
        }
        vector<int> stk;
        auto query = [&](int l, int r) {
            int mn = 1e9;
            travel(l, r, [&](int p) { mn = min(mn, t[p]); });
            return mn;
        };
        for(int i = 1; i <= n; ++i) {
            if(arr[i] == 'C') {
                if(!stk.empty()) {
                    travel(stk.back(), n, [&](int p) { lz[p]--, push(p); });
                    stk.pop_back();
                }
                travel(i, n, [&](int p) { lz[p]++, push(p); });
            } else stk.emplace_back(i);
            for(auto x : que[i]) {
                int z = query(x.x, i) - query(x.x-1, x.x-1);
                int pre = lower_bound(all(stk), x.x) - stk.begin();
                ans[x.y] = ((int)stk.size() - pre) - min(0, z);
            }
        }
        for(int i = 0; i < m; ++i) cout << ans[i] << endl;
    }
};

class Solver {
public:
    void solve(std::istream& in, std::ostream& out) {
        election *obj = new election();
        obj->solve(in, out);
    }
};

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Solver solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}

Compilation message

election.cpp: In member function 'void election::solve(std::istream&, std::ostream&)':
election.cpp:48:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin >> arr+1;
                ~~~^~
election.cpp: In instantiation of 'void election::travel(int, int, const T&, int, int, int) [with T = election::solve(std::istream&, std::ostream&)::<lambda(int, int)>::<lambda(int)>]':
election.cpp:57:60:   required from here
election.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l + r >> 1;
                 ~~^~~
election.cpp: In instantiation of 'void election::travel(int, int, const T&, int, int, int) [with T = election::solve(std::istream&, std::ostream&)::<lambda(int)>]':
election.cpp:63:75:   required from here
election.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
election.cpp: In instantiation of 'void election::travel(int, int, const T&, int, int, int) [with T = election::solve(std::istream&, std::ostream&)::<lambda(int)>]':
election.cpp:66:62:   required from here
election.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23548 KB Output is correct
2 Correct 28 ms 23552 KB Output is correct
3 Correct 31 ms 23552 KB Output is correct
4 Correct 27 ms 23552 KB Output is correct
5 Correct 31 ms 23544 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23548 KB Output is correct
2 Correct 28 ms 23552 KB Output is correct
3 Correct 31 ms 23552 KB Output is correct
4 Correct 27 ms 23552 KB Output is correct
5 Correct 31 ms 23544 KB Output is correct
6 Correct 281 ms 26272 KB Output is correct
7 Correct 229 ms 25664 KB Output is correct
8 Correct 230 ms 25720 KB Output is correct
9 Correct 254 ms 25956 KB Output is correct
10 Correct 244 ms 25852 KB Output is correct
11 Correct 245 ms 26232 KB Output is correct
12 Correct 254 ms 26156 KB Output is correct
13 Correct 303 ms 26300 KB Output is correct
14 Correct 339 ms 26108 KB Output is correct
15 Correct 242 ms 26000 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23548 KB Output is correct
2 Correct 28 ms 23552 KB Output is correct
3 Correct 31 ms 23552 KB Output is correct
4 Correct 27 ms 23552 KB Output is correct
5 Correct 31 ms 23544 KB Output is correct
6 Correct 281 ms 26272 KB Output is correct
7 Correct 229 ms 25664 KB Output is correct
8 Correct 230 ms 25720 KB Output is correct
9 Correct 254 ms 25956 KB Output is correct
10 Correct 244 ms 25852 KB Output is correct
11 Correct 245 ms 26232 KB Output is correct
12 Correct 254 ms 26156 KB Output is correct
13 Correct 303 ms 26300 KB Output is correct
14 Correct 339 ms 26108 KB Output is correct
15 Correct 242 ms 26000 KB Output is correct
16 Correct 1811 ms 42688 KB Output is correct
17 Correct 1556 ms 39800 KB Output is correct
18 Correct 1787 ms 40952 KB Output is correct
19 Correct 1699 ms 42460 KB Output is correct
20 Correct 1718 ms 41848 KB Output is correct
21 Correct 1876 ms 44016 KB Output is correct
22 Correct 2008 ms 43580 KB Output is correct
23 Correct 1880 ms 44312 KB Output is correct
24 Correct 1944 ms 43556 KB Output is correct
25 Correct 1916 ms 42928 KB Output is correct