Submission #1133924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133924		ByeWorld	Election (BOI18_election)	C++20	100 / 100	905 ms	74248 KiB

election

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 5e5+10;
const int SQRT = 610;
const int MAXA = 50;
const int MOD = 1e6+7;
const int INF = 1e18+10;
const int LOG = 30;
const ld EPS = 1e-12;
int sum(int a, int b){ return (a+b)%MOD; }
int mul(int a, int b){ return (1ll*a*b)%MOD; }
void chsum(int &a, int b){ a = (a+b)%MOD; }
void chmul(int &a, int b){ a = (1ll*a*b)%MOD; }

int n,q,a[MAXN], ans[MAXN];
vector <pii> vec[MAXN];

struct seg {
    int st[4*MAXN],laz[4*MAXN];
    void bnc(int id, int l, int r){
        if(laz[id]==0) return;
        st[lf]+=laz[id]; laz[lf]+=laz[id];
        st[rg]+=laz[id]; laz[rg]+=laz[id];
        laz[id] = 0;
    }
    int que(int id, int l, int r, int x, int y){
        if(x<=l && r<=y) return st[id];
        if(r<x || y<l) return INF;
        bnc(id,l,r);
        return min(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
    }
    int upd(int id, int l, int r, int x, int y, int p){
        if(x<=l && r<=y){laz[id]+=p; return st[id] += p; }
        if(r<x || y<l) return st[id];
        bnc(id,l,r);
        return st[id] = min(upd(lf,l,md,x,y,p), upd(rg,md+1,r,x,y,p));
    }
} A, B;
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    string s; cin>>s;s='.'+s;
    for(int i=1; i<=n; i++) a[i] = (s[i]=='C' ? 1 : -1);
    cin>>q;
    for(int i=1; i<=q; i++){
        int l,r;cin>>l>>r;
        vec[l].pb({r, i});
    }
    set <int> t; int lef = 0;
    for(int l=n; l>=1; l--){
        if(s[l]=='C'){
            if(!t.empty()){
                int nx = *t.begin(); t.erase(nx);
                A.upd(1,1,n+1,1,nx,-1); // reactivate
                B.upd(1,1,n+1,nx,n+1,1);
            }
            A.upd(1,1,n+1,1,l,1); // dari n
        } else {
            t.insert(l); B.upd(1,1,n+1,l,n+1,-1);
        }
        for(auto [r, id] : vec[l]){
            ans[id] = -B.que(1,1,n+1,l,r)
                -min(0ll,A.que(1,1,n+1,l,r)-A.que(1,1,n+1,r+1,r+1));
        // cout << l <<' '<<r<<' '<< lef<<"lef\n";
        // for(int i=1; i<=n; i++) cout << A.que(1,1,n+1,i,i) << " \n"[i==n];
        } 
    }
    for(int i=1; i<=q; i++) cout << ans[i] << '\n';
}

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18