oj.uz

Submission #679272

# Submission time Handle Problem Language Result Execution time Memory
679272 2023-01-08T01:29:01 Z gyandevrey6 Election (BOI18_election) C++17
100 / 100
 992 ms 20284 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 = 500010;
struct node {
    int mnl, mnr, mns;
} seg[N*4];

string s;
int pre[N], suf[N];
int n;

inline node merge(const node& x,const 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 {
        return get(l, r, 2*i+2, mid, e);
    }
}

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]) << endl;
    }
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 117 ms 4508 KB Output is correct
7 Correct 125 ms 4556 KB Output is correct
8 Correct 121 ms 4452 KB Output is correct
9 Correct 109 ms 4412 KB Output is correct
10 Correct 116 ms 4340 KB Output is correct
11 Correct 128 ms 4580 KB Output is correct
12 Correct 118 ms 4536 KB Output is correct
13 Correct 117 ms 4592 KB Output is correct
14 Correct 118 ms 4544 KB Output is correct
15 Correct 117 ms 4436 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 117 ms 4508 KB Output is correct
7 Correct 125 ms 4556 KB Output is correct
8 Correct 121 ms 4452 KB Output is correct
9 Correct 109 ms 4412 KB Output is correct
10 Correct 116 ms 4340 KB Output is correct
11 Correct 128 ms 4580 KB Output is correct
12 Correct 118 ms 4536 KB Output is correct
13 Correct 117 ms 4592 KB Output is correct
14 Correct 118 ms 4544 KB Output is correct
15 Correct 117 ms 4436 KB Output is correct
16 Correct 992 ms 19268 KB Output is correct
17 Correct 889 ms 19340 KB Output is correct
18 Correct 937 ms 19372 KB Output is correct
19 Correct 863 ms 18784 KB Output is correct
20 Correct 975 ms 18360 KB Output is correct
21 Correct 991 ms 20276 KB Output is correct
22 Correct 984 ms 20064 KB Output is correct
23 Correct 986 ms 20284 KB Output is correct
24 Correct 990 ms 19880 KB Output is correct
25 Correct 980 ms 19432 KB Output is correct