oj.uz

Submission #867582

# Submission time Handle Problem Language Result Execution time Memory
867582 2023-10-28T20:00:12 Z velislavgarkov Election (BOI18_election) C++14
100 / 100
 979 ms 29968 KB 
#include <iostream>
using namespace std;
const int MAXN=5e5+10;
struct Node {
    int sum;
    int minpr;
    int minsuf;
    int x;
};
int arr[MAXN];
Node tree[4*MAXN];
Node combine (Node a, Node b) {
    Node ans;
    ans.sum=a.sum+b.sum;
    ans.minpr=min(a.minpr,a.sum+b.minpr);
    ans.minsuf=min(b.minsuf,b.sum+a.minsuf);
    ans.x=min(a.minpr+b.minsuf,min(a.x+b.sum,b.x+a.sum));
    ans.x=min(0,ans.x);
    return ans;
}
void build_tree(int node, int l, int r) {
    if (l==r) {
        tree[node]={arr[l],min(0,arr[l]),min(0,arr[l]),min(0,arr[l])};
        return;
    }
    int mid=(l+r)/2;
    build_tree(node*2,l,mid);
    build_tree(node*2+1,mid+1,r);
    tree[node]=combine(tree[node*2],tree[node*2+1]);
}
Node query(int node, int l, int r, int ql, int qr) {
    if (ql>r || qr<l) return {0,0,0,0};
    if (l>=ql && r<=qr) return tree[node];
    int mid=(l+r)/2;
    return combine(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    char ch;
    for (int i=1;i<=n;i++) {
        cin >> ch;
        if (ch=='C') arr[i]=1;
        else arr[i]=-1;
    }
    build_tree(1,1,n);
    int q, l, r;
    cin >> q;
    for (int i=0;i<q;i++) {
        cin >> l >> r;
        Node ans=query(1,1,n,l,r);
        cout << -ans.x << endl;
    }
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 111 ms 6920 KB Output is correct
7 Correct 119 ms 7164 KB Output is correct
8 Correct 112 ms 6860 KB Output is correct
9 Correct 104 ms 6848 KB Output is correct
10 Correct 111 ms 6744 KB Output is correct
11 Correct 136 ms 7208 KB Output is correct
12 Correct 112 ms 7008 KB Output is correct
13 Correct 112 ms 6992 KB Output is correct
14 Correct 124 ms 6876 KB Output is correct
15 Correct 118 ms 7256 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 111 ms 6920 KB Output is correct
7 Correct 119 ms 7164 KB Output is correct
8 Correct 112 ms 6860 KB Output is correct
9 Correct 104 ms 6848 KB Output is correct
10 Correct 111 ms 6744 KB Output is correct
11 Correct 136 ms 7208 KB Output is correct
12 Correct 112 ms 7008 KB Output is correct
13 Correct 112 ms 6992 KB Output is correct
14 Correct 124 ms 6876 KB Output is correct
15 Correct 118 ms 7256 KB Output is correct
16 Correct 921 ms 28528 KB Output is correct
17 Correct 839 ms 28336 KB Output is correct
18 Correct 922 ms 28736 KB Output is correct
19 Correct 829 ms 28384 KB Output is correct
20 Correct 967 ms 27880 KB Output is correct
21 Correct 896 ms 29664 KB Output is correct
22 Correct 979 ms 29632 KB Output is correct
23 Correct 895 ms 29968 KB Output is correct
24 Correct 921 ms 29572 KB Output is correct
25 Correct 903 ms 29400 KB Output is correct