oj.uz

Submission #867581

# Submission time Handle Problem Language Result Execution time Memory
867581 2023-10-28T19:59:39 Z velislavgarkov Election (BOI18_election) C++14
82 / 100
 125 ms 8280 KB 
#include <iostream>
using namespace std;
const int MAXN=1e5+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 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 4 ms 2396 KB Output is correct
5 Correct 4 ms 2392 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 4 ms 2396 KB Output is correct
5 Correct 4 ms 2392 KB Output is correct
6 Correct 125 ms 8184 KB Output is correct
7 Correct 112 ms 7900 KB Output is correct
8 Correct 118 ms 8116 KB Output is correct
9 Correct 110 ms 8016 KB Output is correct
10 Correct 121 ms 8280 KB Output is correct
11 Correct 121 ms 8212 KB Output is correct
12 Correct 117 ms 8232 KB Output is correct
13 Correct 112 ms 8276 KB Output is correct
14 Correct 113 ms 8016 KB Output is correct
15 Correct 111 ms 8020 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 4 ms 2396 KB Output is correct
5 Correct 4 ms 2392 KB Output is correct
6 Correct 125 ms 8184 KB Output is correct
7 Correct 112 ms 7900 KB Output is correct
8 Correct 118 ms 8116 KB Output is correct
9 Correct 110 ms 8016 KB Output is correct
10 Correct 121 ms 8280 KB Output is correct
11 Correct 121 ms 8212 KB Output is correct
12 Correct 117 ms 8232 KB Output is correct
13 Correct 112 ms 8276 KB Output is correct
14 Correct 113 ms 8016 KB Output is correct
15 Correct 111 ms 8020 KB Output is correct
16 Runtime error 5 ms 5464 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -