oj.uz

Submission #1016082

# Submission time Handle Problem Language Result Execution time Memory
1016082 2024-07-07T11:31:28 Z dosts Election (BOI18_election) C++17
100 / 100
 607 ms 74320 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define vvi vector<vi>
const int N = 4e5+1,inf = 2e18,B = 23,MOD = 998244353,LIM = 1e9;    

struct Node {
    int sm,wp,ws,ans;
};

Node merge(Node a,Node b) {
    Node ret;
    ret.sm = a.sm+b.sm;
    ret.wp = max(a.wp,a.sm+b.wp);
    ret.ws = max(b.ws,b.sm+a.ws);
    ret.ans = max({a.ans+b.sm,b.ans+a.sm,a.wp+b.ws});
    return ret;
};

struct ST {
    vector<Node> t;
    ST(int nn) {
        t.assign(4*nn+1,{0,0,0,0});
    } 

    void update(int node,int l,int r,int p,int v) {
        if (l == r) {
            t[node] = {v,max(0ll,v),max(0ll,v),max(0ll,v)};
            return;
        }
        int m = (l+r) >> 1;
        if (p <= m) update(2*node,l,m,p,v);
        else update(2*node+1,m+1,r,p,v);
        t[node] = merge(t[2*node],t[2*node+1]);
    }
    Node query(int node,int l,int r,int L,int R) {
        if (l > R || r < L) return {0,0,0,0};
        if (l >= L && r <= R) return t[node];
        int m = (l+r) >> 1;
        return merge(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
    }

};
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    ST st(n);
    for (int i=1;i<=n;i++) {
        if (s[i-1] == 'C') st.update(1,1,n,i,-1);
        else st.update(1,1,n,i,1);
    }
    int q;
    cin >> q;
    while (q--) {
        int l,r;
        cin >> l >> r;
        cout << st.query(1,1,n,l,r).ans << '\n';
    }
}


                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 60 ms 10576 KB Output is correct
7 Correct 52 ms 10320 KB Output is correct
8 Correct 53 ms 10536 KB Output is correct
9 Correct 47 ms 10320 KB Output is correct
10 Correct 50 ms 10332 KB Output is correct
11 Correct 56 ms 10588 KB Output is correct
12 Correct 50 ms 10680 KB Output is correct
13 Correct 65 ms 10520 KB Output is correct
14 Correct 57 ms 10604 KB Output is correct
15 Correct 52 ms 10576 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 60 ms 10576 KB Output is correct
7 Correct 52 ms 10320 KB Output is correct
8 Correct 53 ms 10536 KB Output is correct
9 Correct 47 ms 10320 KB Output is correct
10 Correct 50 ms 10332 KB Output is correct
11 Correct 56 ms 10588 KB Output is correct
12 Correct 50 ms 10680 KB Output is correct
13 Correct 65 ms 10520 KB Output is correct
14 Correct 57 ms 10604 KB Output is correct
15 Correct 52 ms 10576 KB Output is correct
16 Correct 571 ms 73152 KB Output is correct
17 Correct 512 ms 72828 KB Output is correct
18 Correct 538 ms 73184 KB Output is correct
19 Correct 475 ms 72424 KB Output is correct
20 Correct 541 ms 72248 KB Output is correct
21 Correct 598 ms 74216 KB Output is correct
22 Correct 568 ms 73960 KB Output is correct
23 Correct 607 ms 74320 KB Output is correct
24 Correct 588 ms 73788 KB Output is correct
25 Correct 571 ms 73472 KB Output is correct