oj.uz

Submission #679274

# Submission time Handle Problem Language Result Execution time Memory
679274 2023-01-08T01:30:39 Z gyandevrey6 Election (BOI18_election) C++17
100 / 100
 431 ms 20072 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
 
const int N = 500'010;
struct node {
    int mnl, mnr, mns;
} seg[N*4];
 
string s;
int pre[N], suf[N];
int n;
 
node merge(node x, node y)
{
    node ans;
    ans.mnl = min(x.mnl, y.mnl);
    ans.mnr = min(x.mnr, y.mnr);
    ans.mns = min({x.mns, y.mns, x.mnl + y.mnr});
    return ans;
}
 
void build(int i, int b, int e)
{
    if (e-b == 1) {
        seg[i].mnl = pre[b];
        seg[i].mnr = suf[b];
        seg[i].mns = seg[i].mnl + seg[i].mnr;
        return;
    }
    build(2*i+1, b, (b+e)/2);
    build(2*i+2, (b+e)/2, e);
    seg[i] = merge(seg[2*i+1], seg[2*i+2]);
}
 
node get(int l, int r, int i, int b, int e)
{
    if (l <= b && e <= r)
        return seg[i];
    int mid = (b+e)/2;
    if (l < mid && mid < r) {
        return merge(get(l, r, 2*i+1, b, mid),
                     get(l, r, 2*i+2, mid, e));
    } else if (l < mid) {
        return get(l, r, 2*i+1, b, mid);
    } else if (mid < r) {
        return get(l, r, 2*i+2, mid, e);
    } else {
        for (;;)
            cerr << "666\n";
        *(int *)666 = 666;
        return node{666, 666, 666};
        // >:)
    }
}
 
int main()
{
    cin.tie(0) -> sync_with_stdio(false);
    int q;
    cin >> n;
    cin >> s;
    Loop (i,0,n)
        pre[i+1] = pre[i] + (s[i] == 'C'? 1: -1);
    LoopR (i,0,n)
        suf[i] = suf[i+1] + (s[i] == 'C'? 1: -1);
    build(0, 0, n+1);
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        auto ans = get(l, r+1, 0, 0, n+1);
        cout << -(ans.mns - pre[l] - suf[r]) << '\n';
    }
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 44 ms 4308 KB Output is correct
7 Correct 45 ms 4312 KB Output is correct
8 Correct 45 ms 4436 KB Output is correct
9 Correct 35 ms 4300 KB Output is correct
10 Correct 42 ms 4260 KB Output is correct
11 Correct 42 ms 4396 KB Output is correct
12 Correct 41 ms 4404 KB Output is correct
13 Correct 41 ms 4480 KB Output is correct
14 Correct 41 ms 4384 KB Output is correct
15 Correct 46 ms 4512 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 44 ms 4308 KB Output is correct
7 Correct 45 ms 4312 KB Output is correct
8 Correct 45 ms 4436 KB Output is correct
9 Correct 35 ms 4300 KB Output is correct
10 Correct 42 ms 4260 KB Output is correct
11 Correct 42 ms 4396 KB Output is correct
12 Correct 41 ms 4404 KB Output is correct
13 Correct 41 ms 4480 KB Output is correct
14 Correct 41 ms 4384 KB Output is correct
15 Correct 46 ms 4512 KB Output is correct
16 Correct 426 ms 19068 KB Output is correct
17 Correct 355 ms 19136 KB Output is correct
18 Correct 375 ms 19040 KB Output is correct
19 Correct 308 ms 18640 KB Output is correct
20 Correct 400 ms 18144 KB Output is correct
21 Correct 431 ms 20072 KB Output is correct
22 Correct 428 ms 19876 KB Output is correct
23 Correct 427 ms 20064 KB Output is correct
24 Correct 423 ms 19672 KB Output is correct
25 Correct 417 ms 19388 KB Output is correct