oj.uz

Submission #679276

# Submission time Handle Problem Language Result Execution time Memory
679276 2023-01-08T01:36:20 Z gyandevrey6 Election (BOI18_election) C++17
0 / 100
 4 ms 340 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;

node ans;

const node& merge(const node& x,const node& y)
{
    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]);
}

const 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;
        ans = get(l, r+1, 0, 0, n+1);
        cout << -(ans.mns - pre[l] - suf[r]) << endl;
    }
}

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -