oj.uz

Submission #779673

# Submission time Handle Problem Language Result Execution time Memory
779673 2023-07-11T16:03:14 Z vjudge1 Election (BOI18_election) C++17
100 / 100
 651 ms 50032 KB 
//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 5e5 + 1;
int n, q, res[N + 1];
int pref[N + 1], suf[N + 1], a[N + 1];
vector<pair<int, int> > query[N + 1];
struct SegmentTree
{
    int tree[4 * N + 1], lazy[4 * N + 1];
    void buildtree(int v, int TreeL, int TreeR)
    {
        if (TreeL == TreeR)
        {
            tree[v] = suf[TreeL];
            return ;
        }
        int mid = (TreeL + TreeR)/2;
        buildtree(v * 2, TreeL, mid);
        buildtree(v * 2 + 1, mid + 1, TreeR);
        tree[v] = min(tree[2 * v], tree[2 * v + 1]);
    }
    void push(int v)
    {
        if (!lazy[v])
        {
            return ;
        }
        int d = lazy[v];
        lazy[v] = 0;
        lazy[2 * v] += d;
        lazy[2 * v + 1] += d;
        tree[2 * v] += d;
        tree[2 * v + 1] += d;
    }
    void add(int v, int TreeL, int TreeR, int L, int R, int val)
    {
        if (L > R)
        {
            return ;
        }
        if (TreeL == L && TreeR == R)
        {
            tree[v] += val;
            lazy[v] += val;
            return ;
        }
        int mid = (TreeL + TreeR)/2;
        push(v);
        add(v * 2, TreeL, mid, L, min(R, mid), val);
        add(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R, val);
        tree[v] = min(tree[2 * v], tree[2 * v + 1]);
    }
    int get(int v, int TreeL, int TreeR, int L, int R)
    {
        if (L > R)
        {
            return 1e9;
        }
        if (TreeL == L && TreeR == R)
        {
            return tree[v];
        }
        int mid = (TreeL + TreeR)/2;
        push(v);
        return min(get(v * 2, TreeL, mid, L, min(R, mid)), get(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R));
    }
} tree;
void read()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        char c;
        cin >> c;
        a[i] = (c == 'C' ? 1 : -1);
        pref[i] = pref[i - 1] + a[i];
    }
    for (int i = n; i >= 1; -- i)
    {
        suf[i] = suf[i + 1] + a[i];
    }
    tree.buildtree(1, 1, n + 1);
}
void solve()
{
    cin >> q;
    for (int i = 1; i <= q; ++ i)
    {
        int l, r;
        cin >> l >> r;
        query[l].emplace_back(r, i);
    }
    vector<int> st;
    for (int l = n; l >= 0; -- l)
    {
        while(!st.empty() && pref[l] <= pref[st.back()])
        {
            tree.add(1, 1, n + 1, 1, st.back(), -1);
            st.pop_back();
        }
        for (auto [r, i] : query[l + 1])
        {
            res[i] += upper_bound(st.rbegin(), st.rend(), r) - st.rbegin();
            int t = tree.get(1, 1, n + 1, l + 1, r) - tree.get(1, 1, n + 1, r + 1, r + 1);
            res[i] += max(0, -t);
        }
        st.push_back(l);
        tree.add(1, 1, n + 1, 1, l, 1);
    }
    for (int i = 1; i <= q; ++ i)
    {
        cout << res[i] << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 9 ms 12216 KB Output is correct
3 Correct 9 ms 12220 KB Output is correct
4 Correct 8 ms 12252 KB Output is correct
5 Correct 8 ms 12176 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 9 ms 12216 KB Output is correct
3 Correct 9 ms 12220 KB Output is correct
4 Correct 8 ms 12252 KB Output is correct
5 Correct 8 ms 12176 KB Output is correct
6 Correct 71 ms 17876 KB Output is correct
7 Correct 61 ms 17368 KB Output is correct
8 Correct 70 ms 17432 KB Output is correct
9 Correct 69 ms 17740 KB Output is correct
10 Correct 69 ms 17764 KB Output is correct
11 Correct 78 ms 18040 KB Output is correct
12 Correct 70 ms 18076 KB Output is correct
13 Correct 83 ms 18212 KB Output is correct
14 Correct 69 ms 17968 KB Output is correct
15 Correct 69 ms 17888 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 9 ms 12216 KB Output is correct
3 Correct 9 ms 12220 KB Output is correct
4 Correct 8 ms 12252 KB Output is correct
5 Correct 8 ms 12176 KB Output is correct
6 Correct 71 ms 17876 KB Output is correct
7 Correct 61 ms 17368 KB Output is correct
8 Correct 70 ms 17432 KB Output is correct
9 Correct 69 ms 17740 KB Output is correct
10 Correct 69 ms 17764 KB Output is correct
11 Correct 78 ms 18040 KB Output is correct
12 Correct 70 ms 18076 KB Output is correct
13 Correct 83 ms 18212 KB Output is correct
14 Correct 69 ms 17968 KB Output is correct
15 Correct 69 ms 17888 KB Output is correct
16 Correct 605 ms 48312 KB Output is correct
17 Correct 458 ms 44276 KB Output is correct
18 Correct 546 ms 45460 KB Output is correct
19 Correct 542 ms 47024 KB Output is correct
20 Correct 612 ms 47368 KB Output is correct
21 Correct 651 ms 49764 KB Output is correct
22 Correct 595 ms 49316 KB Output is correct
23 Correct 614 ms 50032 KB Output is correct
24 Correct 584 ms 49308 KB Output is correct
25 Correct 588 ms 48588 KB Output is correct