oj.uz

Submission #681219

# Submission time Handle Problem Language Result Execution time Memory
681219 2023-01-12T14:42:51 Z Tien_Noob Election (BOI18_election) C++17
100 / 100
 827 ms 50120 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 8 ms 12212 KB Output is correct
3 Correct 8 ms 12248 KB Output is correct
4 Correct 9 ms 12352 KB Output is correct
5 Correct 8 ms 12224 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 8 ms 12212 KB Output is correct
3 Correct 8 ms 12248 KB Output is correct
4 Correct 9 ms 12352 KB Output is correct
5 Correct 8 ms 12224 KB Output is correct
6 Correct 88 ms 17856 KB Output is correct
7 Correct 86 ms 17340 KB Output is correct
8 Correct 80 ms 17496 KB Output is correct
9 Correct 79 ms 17816 KB Output is correct
10 Correct 93 ms 17752 KB Output is correct
11 Correct 97 ms 18124 KB Output is correct
12 Correct 109 ms 18016 KB Output is correct
13 Correct 94 ms 18252 KB Output is correct
14 Correct 89 ms 17980 KB Output is correct
15 Correct 98 ms 17916 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 8 ms 12212 KB Output is correct
3 Correct 8 ms 12248 KB Output is correct
4 Correct 9 ms 12352 KB Output is correct
5 Correct 8 ms 12224 KB Output is correct
6 Correct 88 ms 17856 KB Output is correct
7 Correct 86 ms 17340 KB Output is correct
8 Correct 80 ms 17496 KB Output is correct
9 Correct 79 ms 17816 KB Output is correct
10 Correct 93 ms 17752 KB Output is correct
11 Correct 97 ms 18124 KB Output is correct
12 Correct 109 ms 18016 KB Output is correct
13 Correct 94 ms 18252 KB Output is correct
14 Correct 89 ms 17980 KB Output is correct
15 Correct 98 ms 17916 KB Output is correct
16 Correct 798 ms 48300 KB Output is correct
17 Correct 657 ms 44264 KB Output is correct
18 Correct 663 ms 45492 KB Output is correct
19 Correct 665 ms 46936 KB Output is correct
20 Correct 812 ms 47344 KB Output is correct
21 Correct 817 ms 49744 KB Output is correct
22 Correct 827 ms 49320 KB Output is correct
23 Correct 802 ms 50120 KB Output is correct
24 Correct 765 ms 49344 KB Output is correct
25 Correct 817 ms 48588 KB Output is correct