oj.uz

Submission #336182

# Submission time Handle Problem Language Result Execution time Memory
336182 2020-12-15T00:57:04 Z HynDuf Election (BOI18_election) C++11
100 / 100
 909 ms 46968 KB 
#include <bits/stdc++.h>

#define task "E"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int N = 5e5 + 2, INF = 1e9 + 3172;
int n, q, ans[N], a[N];
string s;
vii qu[N];
struct Node
{
    int sum, suf;
    Node() {}
    Node(int _sum, int _suf) : sum(_sum), suf(_suf) {}
} it[N << 2];
void build(int id, int l, int r)
{
    if (l == r)
    {
        it[id] = Node(a[l], min(a[l], 0));
        return;
    }
    int m = (l + r) >> 1;
    build(id << 1, l, m);
    build((id << 1) | 1, m + 1, r);
    it[id] = Node(it[id << 1].sum + it[(id << 1) | 1].sum, min(it[id << 1].suf + it[(id << 1) | 1].sum, it[(id << 1) | 1].suf));
}
void update(int id, int l, int r, int p, int v)
{
    if (l > p || r < p) return;
    if (l == r)
    {
        it[id] = Node(v, min(v, 0));
        return;
    }
    int m = (l + r) >> 1;
    update(id << 1, l, m, p, v);
    update((id << 1) | 1, m + 1, r, p, v);
    it[id] = Node(it[id << 1].sum + it[(id << 1) | 1].sum, min(it[id << 1].suf + it[(id << 1) | 1].sum, it[(id << 1) | 1].suf));
}
Node query(int id, int l, int r, int L, int R)
{
    if (l > R || r < L) return Node(0, 0);
    if (L <= l && r <= R) return it[id];
    int m = (l + r) >> 1;
    Node Le = query(id << 1, l, m, L, R), Ri = query((id << 1) | 1, m + 1, r, L, R);
    return Node(Le.sum + Ri.sum, min(Le.suf + Ri.sum, Ri.suf));
}
int main()
{
#ifdef HynDuf
    freopen(task".in", "r", stdin);
    //freopen(task".out", "w", stdout);
#else
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
    cin >> n >> s >> q;
    rep(i, 1, q)
    {
        int l, r;
        cin >> l >> r;
        qu[l].eb(r, i);
    }
    rep(i, 1, n) a[i] = (s[i - 1] == 'C' ? 1 : -1);
    build(1, 1, n);
    vi st;
    Rep(i, n, 1)
    {
        if (a[i] == 1)
        {
            if (!st.empty())
            {
                update(1, 1, n, st.back(), a[st.back()]);
                st.pop_back();
            }
        } else
        {
            update(1, 1, n, i, 0);
            st.pb(i);
        }
        for (const ii &Q : qu[i])
        {
//            PR(st, 0, SZ(st) - 1);
            ans[Q.S] = upper_bound(st.rbegin(), st.rend(), Q.F) - st.rbegin();
            Node res = query(1, 1, n, i, Q.F);
            ans[Q.S] -= res.suf;
        }
    }
    rep(i, 1, q) cout << ans[i] << '\n';
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12268 KB Output is correct
2 Correct 10 ms 12268 KB Output is correct
3 Correct 9 ms 12268 KB Output is correct
4 Correct 10 ms 12268 KB Output is correct
5 Correct 10 ms 12268 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12268 KB Output is correct
2 Correct 10 ms 12268 KB Output is correct
3 Correct 9 ms 12268 KB Output is correct
4 Correct 10 ms 12268 KB Output is correct
5 Correct 10 ms 12268 KB Output is correct
6 Correct 100 ms 17644 KB Output is correct
7 Correct 95 ms 17004 KB Output is correct
8 Correct 81 ms 17132 KB Output is correct
9 Correct 83 ms 17388 KB Output is correct
10 Correct 89 ms 17388 KB Output is correct
11 Correct 95 ms 17644 KB Output is correct
12 Correct 92 ms 17644 KB Output is correct
13 Correct 99 ms 18004 KB Output is correct
14 Correct 96 ms 17644 KB Output is correct
15 Correct 83 ms 17644 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12268 KB Output is correct
2 Correct 10 ms 12268 KB Output is correct
3 Correct 9 ms 12268 KB Output is correct
4 Correct 10 ms 12268 KB Output is correct
5 Correct 10 ms 12268 KB Output is correct
6 Correct 100 ms 17644 KB Output is correct
7 Correct 95 ms 17004 KB Output is correct
8 Correct 81 ms 17132 KB Output is correct
9 Correct 83 ms 17388 KB Output is correct
10 Correct 89 ms 17388 KB Output is correct
11 Correct 95 ms 17644 KB Output is correct
12 Correct 92 ms 17644 KB Output is correct
13 Correct 99 ms 18004 KB Output is correct
14 Correct 96 ms 17644 KB Output is correct
15 Correct 83 ms 17644 KB Output is correct
16 Correct 851 ms 45160 KB Output is correct
17 Correct 664 ms 41156 KB Output is correct
18 Correct 740 ms 42240 KB Output is correct
19 Correct 679 ms 43776 KB Output is correct
20 Correct 791 ms 44096 KB Output is correct
21 Correct 909 ms 46588 KB Output is correct
22 Correct 837 ms 46080 KB Output is correct
23 Correct 858 ms 46968 KB Output is correct
24 Correct 818 ms 46332 KB Output is correct
25 Correct 728 ms 45568 KB Output is correct