oj.uz

Submission #1108868

# Submission time Handle Problem Language Result Execution time Memory
1108868 2024-11-05T12:42:36 Z 0pt1mus23 Election (BOI18_election) C++14
100 / 100
 454 ms 44512 KB 
// fast.cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
int nxt(){ int x;cin>>x; return x; }

const int mod = 1e9 +7, sze = 5e5 +10, inf = LLONG_MAX, LG = 20;
string s;
int n;
struct st{
    int sum=0;
    int pf=0;
    int sf=0;
    int res=0;
} T[sze*4];

st combine(st a,st b){
    st c;
    c.sum = a.sum + b.sum;
    c.pf = max(a.pf, a.sum + b.pf);
    c.sf = max(b.sf, b.sum + a.sf);
    c.res=max( { a.pf  + b.sf , a.res + b.sum, a.sum + b.res });
    return c;
}
void build(int node,int l,int r){
    if(l==r){
        if(s[l]=='C'){
            T[node]={-1,0,0,0};
        }
        else{
            T[node]={1,1,1,1};
        }
        return ;
    }
    int mid = (l+r)/2;
    build(2*node,l,mid);
    build(2*node +1,mid+1,r);
    T[node]=combine(T[node*2],T[node*2 +1]);
}
st qry(int l,int r,int node=1,int lx=0,int rx=n-1){
    if(l>rx || r<lx){
        return {0,0,0,0};
    }
    if(lx>=l && rx<=r){
        return T[node];
    }
    int mid = (lx+rx)/2;
    return combine(qry(l,r,2*node ,lx,mid), qry(l,r,2*node +1,mid+1,rx));

}
void rush(){
    cin>>n;
    cin>>s;
    build(1,0,n-1);
    int q;
    cin>>q;
    while(q--){
        int l=nxt()-1,r=nxt()-1;
        cout<<qry(l,r,1,0,n-1).res<<endl;
    }
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        rush();
    }
 
    return 0;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 46 ms 10064 KB Output is correct
7 Correct 44 ms 10068 KB Output is correct
8 Correct 52 ms 10400 KB Output is correct
9 Correct 43 ms 9976 KB Output is correct
10 Correct 43 ms 10072 KB Output is correct
11 Correct 44 ms 10136 KB Output is correct
12 Correct 42 ms 10064 KB Output is correct
13 Correct 43 ms 10312 KB Output is correct
14 Correct 42 ms 10064 KB Output is correct
15 Correct 48 ms 10056 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 46 ms 10064 KB Output is correct
7 Correct 44 ms 10068 KB Output is correct
8 Correct 52 ms 10400 KB Output is correct
9 Correct 43 ms 9976 KB Output is correct
10 Correct 43 ms 10072 KB Output is correct
11 Correct 44 ms 10136 KB Output is correct
12 Correct 42 ms 10064 KB Output is correct
13 Correct 43 ms 10312 KB Output is correct
14 Correct 42 ms 10064 KB Output is correct
15 Correct 48 ms 10056 KB Output is correct
16 Correct 388 ms 43484 KB Output is correct
17 Correct 364 ms 43368 KB Output is correct
18 Correct 400 ms 43484 KB Output is correct
19 Correct 350 ms 42972 KB Output is correct
20 Correct 428 ms 42716 KB Output is correct
21 Correct 436 ms 44512 KB Output is correct
22 Correct 446 ms 44340 KB Output is correct
23 Correct 419 ms 44508 KB Output is correct
24 Correct 445 ms 44328 KB Output is correct
25 Correct 454 ms 43732 KB Output is correct