oj.uz

Submission #867198

# Submission time Handle Problem Language Result Execution time Memory
867198 2023-10-27T20:39:30 Z Markynoodle Election (BOI18_election) C++17
100 / 100
 1204 ms 20308 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 4 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 4 ms 344 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 152 ms 4936 KB Output is correct
7 Correct 148 ms 4808 KB Output is correct
8 Correct 148 ms 5428 KB Output is correct
9 Correct 147 ms 4760 KB Output is correct
10 Correct 147 ms 4748 KB Output is correct
11 Correct 148 ms 4948 KB Output is correct
12 Correct 158 ms 5020 KB Output is correct
13 Correct 147 ms 4944 KB Output is correct
14 Correct 147 ms 4944 KB Output is correct
15 Correct 153 ms 5204 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 152 ms 4936 KB Output is correct
7 Correct 148 ms 4808 KB Output is correct
8 Correct 148 ms 5428 KB Output is correct
9 Correct 147 ms 4760 KB Output is correct
10 Correct 147 ms 4748 KB Output is correct
11 Correct 148 ms 4948 KB Output is correct
12 Correct 158 ms 5020 KB Output is correct
13 Correct 147 ms 4944 KB Output is correct
14 Correct 147 ms 4944 KB Output is correct
15 Correct 153 ms 5204 KB Output is correct
16 Correct 1171 ms 19572 KB Output is correct
17 Correct 1147 ms 19324 KB Output is correct
18 Correct 1167 ms 19568 KB Output is correct
19 Correct 1093 ms 18980 KB Output is correct
20 Correct 1204 ms 18624 KB Output is correct
21 Correct 1161 ms 20284 KB Output is correct
22 Correct 1173 ms 20040 KB Output is correct
23 Correct 1188 ms 20308 KB Output is correct
24 Correct 1183 ms 19964 KB Output is correct
25 Correct 1158 ms 19724 KB Output is correct