oj.uz

Submission #1034074

# Submission time Handle Problem Language Result Execution time Memory
1034074 2024-07-25T09:29:27 Z Andrey Election (BOI18_election) C++14
100 / 100
 340 ms 44312 KB 
#include<bits/stdc++.h>
using namespace std;

vector<int> haha(500001);
vector<int> brl(2000001);
vector<int> brr(2000001);
vector<int> wow(2000001);
vector<int> sb(2000001);

pair<pair<int,int>,pair<int,int>> merge(pair<pair<int,int>,pair<int,int>> a, pair<pair<int,int>,pair<int,int>> b) {
    pair<int,int> c = a.first,d = a.second,e = b.first,f = b.second;
    int sb = c.second+e.second;
    int br1 = d.first+max(0,f.first-(c.second+d.first));
    int br2 = f.second+max(0,d.second-(e.second+f.second));
    int x = max(0,e.first-f.second-(c.second+d.first));
    int y = max(0,c.first-d.first-(e.second+f.second+x));
    return {{d.first+f.second+x+y,sb},{br1,br2}};
}

void build(int l, int r, int x) {
    if(l == r) {
        sb[x] = haha[l];
        if(haha[l] == -1) {
            brl[x] = 1;
            brr[x] = 1;
            wow[x] = 1;
        }
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    pair<pair<int,int>,pair<int,int>> c = merge({{wow[x*2],sb[x*2]},{brl[x*2],brr[x*2]}},{{wow[x*2+1],sb[x*2+1]},{brl[x*2+1],brr[x*2+1]}});
    sb[x] = c.first.second;
    brl[x] = c.second.first;
    brr[x] = c.second.second;
    wow[x] = c.first.first;
}

pair<pair<int,int>,pair<int,int>> calc(int l, int r, int ql, int qr, int x) {
    if(l == ql && r == qr) {
        return {{wow[x],sb[x]},{brl[x],brr[x]}};
    }
    int mid = (l+r)/2;
    if(qr <= mid) {
        return calc(l,mid,ql,qr,x*2);
    }
    else if(ql > mid) {
        return calc(mid+1,r,ql,qr,x*2+1);
    }
    else {
        return merge(calc(l,mid,ql,mid,x*2),calc(mid+1,r,mid+1,qr,x*2+1));
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,q,l,r;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        char a;
        cin >> a;
        if(a == 'C') {
            haha[i] = 1;
        }
        else {
            haha[i] = -1;
        }
    }
    build(1,n,1);
    cin >> q;
    for(int i = 0; i < q; i++) {
        cin >> l >> r;
        cout << calc(1,n,l,r,1).first.first << "\n";
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33624 KB Output is correct
2 Correct 17 ms 33716 KB Output is correct
3 Correct 15 ms 33628 KB Output is correct
4 Correct 13 ms 33772 KB Output is correct
5 Correct 13 ms 33628 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33624 KB Output is correct
2 Correct 17 ms 33716 KB Output is correct
3 Correct 15 ms 33628 KB Output is correct
4 Correct 13 ms 33772 KB Output is correct
5 Correct 13 ms 33628 KB Output is correct
6 Correct 48 ms 34928 KB Output is correct
7 Correct 46 ms 34908 KB Output is correct
8 Correct 53 ms 34932 KB Output is correct
9 Correct 40 ms 34648 KB Output is correct
10 Correct 46 ms 34648 KB Output is correct
11 Correct 47 ms 34900 KB Output is correct
12 Correct 47 ms 34760 KB Output is correct
13 Correct 48 ms 34900 KB Output is correct
14 Correct 57 ms 34900 KB Output is correct
15 Correct 45 ms 34896 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33624 KB Output is correct
2 Correct 17 ms 33716 KB Output is correct
3 Correct 15 ms 33628 KB Output is correct
4 Correct 13 ms 33772 KB Output is correct
5 Correct 13 ms 33628 KB Output is correct
6 Correct 48 ms 34928 KB Output is correct
7 Correct 46 ms 34908 KB Output is correct
8 Correct 53 ms 34932 KB Output is correct
9 Correct 40 ms 34648 KB Output is correct
10 Correct 46 ms 34648 KB Output is correct
11 Correct 47 ms 34900 KB Output is correct
12 Correct 47 ms 34760 KB Output is correct
13 Correct 48 ms 34900 KB Output is correct
14 Correct 57 ms 34900 KB Output is correct
15 Correct 45 ms 34896 KB Output is correct
16 Correct 331 ms 43344 KB Output is correct
17 Correct 283 ms 42968 KB Output is correct
18 Correct 333 ms 43072 KB Output is correct
19 Correct 238 ms 42580 KB Output is correct
20 Correct 292 ms 42340 KB Output is correct
21 Correct 340 ms 44116 KB Output is correct
22 Correct 307 ms 44116 KB Output is correct
23 Correct 287 ms 44312 KB Output is correct
24 Correct 328 ms 44116 KB Output is correct
25 Correct 307 ms 43344 KB Output is correct