oj.uz

Submission #570117

# Submission time Handle Problem Language Result Execution time Memory
570117 2022-05-28T15:14:52 Z PanTkd Election (BOI18_election) C++17
100 / 100
 1420 ms 44364 KB 
//
//  main.cpp
//
//  Created by Panagiotis Chadjicostas on
//  Copyright © Panagiotis Hadjicostas. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
#define fo(i,a,b) for(int i = a; i<=b; i++)
#define f(i,b) for(int i=0;i<b;i++)
#define F first
#define S second
#define sz size
#define ls s,m,idx<<1
#define rs m+1,e,idx<<1|1
const ll MOD=ll(1e9)+7;
const ll MAXN=2*ll(1e6);
void checker(){
    ll n=rand()%20+2;
    vi a(n,ll());
    for(ll i=0;i<n;i++){
        a[i]=rand()%20+2;
    }
    for(ll b=0;b<(1<<n);b++){
        vi on,off;
        for(ll i=0;i<n;i++){
            if(i&(1<<i)){
                on.push_back(i);
            }
            else{
                off.push_back(i);
            }
        }
    }
}
///////////////////////////////////////////////////////////////////////

struct ss{
    ll pr=0,sf=0,s=0,ans=0;
};
ss seg[2000002];
ss miden;
ss push(ss a,ss b){
    ss cc;
    cc.pr=max(a.pr,a.s+b.pr);
    cc.sf=max(b.sf,b.s+a.sf);
    cc.s=a.s+b.s;
    cc.ans = max(a.pr+b.sf, max(a.ans+b.s, b.ans+a.s));
    return cc;
}
void update(ll idx,ll s,ll e,ll u,ll val){
    if(s==e){
        seg[idx].pr = max(seg[idx].pr, val);
        seg[idx].sf = max(seg[idx].sf, val);
        seg[idx].s += val;
        seg[idx].ans = ((val == -1) ? 0 : 1);
        return;
    }
    ll m=(s+e)>>1;
    if(u<=m){
        update(idx<<1,s,m,u,val);
    }
    else{
        update(idx<<1|1,m+1,e,u,val);
    }
    seg[idx]=push(seg[idx<<1],seg[idx<<1|1]);
}
ss query(ll idx,ll s,ll e,ll qs,ll qe){
    if(s>qe||e<qs)
        return miden;
    if(s>=qs&&e<=qe){
        return seg[idx];
    }
    ll m=(s+e)>>1;
    ss q1=query(idx<<1,s,m,qs,qe);
    ss q2=query(idx<<1|1,m+1,e,qs,qe);
    return push(q1,q2);
}
void solve(){
    ll n;cin>>n;
    string s;cin>>s;
    s=' '+s;
    for(ll i=1;i<=n;i++){
        update(1, 1, n, i, ((s[i] == 'C') ? -1 : 1));
    }
    ll q;cin>>q;

    while(q--){
        ll l,r;cin>>l>>r;
        cout<<query(1,1,n,l,r).ans<<endl;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;//cin>>t;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 148 ms 9312 KB Output is correct
7 Correct 168 ms 9840 KB Output is correct
8 Correct 173 ms 9744 KB Output is correct
9 Correct 140 ms 9752 KB Output is correct
10 Correct 196 ms 9708 KB Output is correct
11 Correct 181 ms 9936 KB Output is correct
12 Correct 159 ms 9916 KB Output is correct
13 Correct 173 ms 9988 KB Output is correct
14 Correct 174 ms 9964 KB Output is correct
15 Correct 166 ms 9844 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 148 ms 9312 KB Output is correct
7 Correct 168 ms 9840 KB Output is correct
8 Correct 173 ms 9744 KB Output is correct
9 Correct 140 ms 9752 KB Output is correct
10 Correct 196 ms 9708 KB Output is correct
11 Correct 181 ms 9936 KB Output is correct
12 Correct 159 ms 9916 KB Output is correct
13 Correct 173 ms 9988 KB Output is correct
14 Correct 174 ms 9964 KB Output is correct
15 Correct 166 ms 9844 KB Output is correct
16 Correct 1315 ms 43328 KB Output is correct
17 Correct 1219 ms 42936 KB Output is correct
18 Correct 1252 ms 43224 KB Output is correct
19 Correct 1161 ms 42716 KB Output is correct
20 Correct 1388 ms 42500 KB Output is correct
21 Correct 1347 ms 44268 KB Output is correct
22 Correct 1340 ms 44172 KB Output is correct
23 Correct 1310 ms 44364 KB Output is correct
24 Correct 1277 ms 44076 KB Output is correct
25 Correct 1420 ms 43536 KB Output is correct