oj.uz

Submission #867197

# Submission time Handle Problem Language Result Execution time Memory
867197 2023-10-27T20:38:05 Z Markynoodle Election (BOI18_election) C++17
100 / 100
 480 ms 28024 KB 
#include<bits/stdc++.h>
using namespace std;

#define all(x) x.begin(),x.end()
#define ll long long
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
auto cmp = [](int a, int b){return a > b;};
auto cmp1 = [](pair<ll,ll> a, pair<ll,ll> b){
    if(a.first == b.first)return a.second > b.second;
    return a.first < b.first;
    };
ll mod = 1000000007;


#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr);

int nextpowerof2(int n){
    return 1<<(__lg(n-1)+1);
}

struct node{
    int sum;
    int pre;
    int suf;
    int ans;
};

node merge(node a, node b){
    return {a.sum + b.sum, max(a.pre, a.sum + b.pre), max(b.suf, b.sum + a.suf), max({0, a.pre + b.suf, a.ans + b.sum, a.sum + b.ans})};
}

struct segtree{
    vector<node> tree;
    segtree(int n) : tree(){
        tree.assign(n, {0,0,0,0});
    };
    void update(int l, int r, int pos, int i, int x){

        if(l == i && l + 1 == r){
            tree[pos] = {x, max(x, 0), max(x, 0), max(x, 0)};
            return;
        }
        if(i < l || r <= i)return;
        int m = l + (r - l)/2;

        update(l, m, pos*2, i, x);
        update(m, r, pos*2 + 1, i, x);
        tree[pos] = merge(tree[pos*2], tree[pos*2 + 1]);
        return;
    }

    node query(int l, int r, int pos, int ql, int qr){
        if(ql <= l && r <= qr)return tree[pos];
        if(qr <= l || r <= ql)return {0,0,0,0};
        int m = l + (r - l)/2;
        return merge(query(l, m, pos*2, ql, qr), query(m, r, pos*2 + 1, ql, qr));
    }
};

int main(){
    fastIO
    int n;
    int q;
    cin>>n;
    int npo2 = nextpowerof2(n);
    segtree sgt(npo2 * 2);
    string s;
    cin>>s;
    for(int i =0; i<n; i++){
        if(s[i] == 'C')sgt.update(0, npo2, 1, i, -1);
        if(s[i] == 'T')sgt.update(0, npo2, 1, i, 1);
    }
    cin>>q;
    int x, y;

    for(int i =0; i<q;i++){

        cin>>x>>y;
        x--;
        cout<<sgt.query(0, npo2, 1, x, y).ans<<"\n";
    }
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 552 KB Output is correct
3 Correct 1 ms 540 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 552 KB Output is correct
3 Correct 1 ms 540 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 65 ms 5724 KB Output is correct
7 Correct 49 ms 5712 KB Output is correct
8 Correct 48 ms 5724 KB Output is correct
9 Correct 45 ms 5748 KB Output is correct
10 Correct 58 ms 5712 KB Output is correct
11 Correct 50 ms 6008 KB Output is correct
12 Correct 49 ms 5980 KB Output is correct
13 Correct 50 ms 5976 KB Output is correct
14 Correct 50 ms 5968 KB Output is correct
15 Correct 52 ms 5968 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 552 KB Output is correct
3 Correct 1 ms 540 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 65 ms 5724 KB Output is correct
7 Correct 49 ms 5712 KB Output is correct
8 Correct 48 ms 5724 KB Output is correct
9 Correct 45 ms 5748 KB Output is correct
10 Correct 58 ms 5712 KB Output is correct
11 Correct 50 ms 6008 KB Output is correct
12 Correct 49 ms 5980 KB Output is correct
13 Correct 50 ms 5976 KB Output is correct
14 Correct 50 ms 5968 KB Output is correct
15 Correct 52 ms 5968 KB Output is correct
16 Correct 454 ms 27112 KB Output is correct
17 Correct 405 ms 26816 KB Output is correct
18 Correct 433 ms 27056 KB Output is correct
19 Correct 365 ms 26224 KB Output is correct
20 Correct 428 ms 26600 KB Output is correct
21 Correct 434 ms 27880 KB Output is correct
22 Correct 466 ms 27872 KB Output is correct
23 Correct 445 ms 28024 KB Output is correct
24 Correct 474 ms 27672 KB Output is correct
25 Correct 480 ms 27112 KB Output is correct