oj.uz

Submission #376632

# Submission time Handle Problem Language Result Execution time Memory
376632 2021-03-11T21:31:34 Z couplefire Election (BOI18_election) C++17
0 / 100
 15 ms 8684 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 524288

struct Seg{
    int tree[2*MAXN] = {0};
    Seg(){}
    void upd(int pos, int val, int tl = 0, int tr = MAXN-1, int v = 1){
        if(tl > pos || tr < pos) return;
        if(tl == tr){
            tree[v] = val;
            return;
        }
        int mid = (tl+tr)/2;
        upd(pos, val, tl, mid, v*2);
        upd(pos, val, mid+1, tr, v*2+1);
        tree[v] = max(tree[v*2], tree[v*2+1]);
    }
    int query(int l, int r, int tl = 0, int tr = MAXN-1, int v = 1){
        if(tl > r || tr < l) return -MAXN;
        if(l <= tl && tr <= r) return tree[v];
        int tm = (tl+tr)/2;
        return max(query(l, r, tl, tm, v*2), query(l, r, tm+1, tr, v*2+1));
    }
} leftseg, rightseg;

int n, q;
int arr[MAXN];
int leftval[MAXN], rightval[MAXN];
string s;

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s;
    for(int i = 0; i<n; i++){
        arr[i+1] = (s[i] == 'C')?-1:1;
    }
    for(int i = 1; i<=n; i++) leftval[i] = arr[i]+leftval[i-1];
    for(int i = n; i>=1; i--) rightval[i] = arr[i]+rightval[i+1];
    for(int i = 1; i<=n; i++) leftseg.upd(i, leftval[i]), rightseg.upd(i, rightval[i]);
    cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        cout << max(0, max(leftseg.query(l, r)-leftval[l-1], rightseg.query(l, r)-rightval[r+1])) << endl;
    }
}

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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