Submission #457591

#	Time	Username	Problem	Language	Result	Execution time	Memory
457591		Fidisk	Election (BOI18_election)	C++14	0 / 100	2 ms	460 KiB

election

#include <bits/stdc++.h>
using namespace std;

#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>(aaaa-1))&1)

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<pair<int,int>,pair<int,int>> piiii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
typedef pair<long double,long double> pld;
typedef pair<pair<long double,long double>,long double> plld;
typedef pair<long double,long long> pdl;

const ll base=361;
const ll mod=1e9+7;
const ll mod2=1e9;
const ld eps=1e-3;
const ld eps2=1e-7;
const ll maxn=1e16;
const ld pi=acos(-1);
const ll delta=1e5+7;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};

const int dxkn[8]={1,1,2,2,-1,-1,-2,-2};
const int dykn[8]={2,-2,1,-1,2,-2,1,-1};
const int dxki[8]={1,1,1,0,0,-1,-1,-1};
const int dyki[8]={1,0,-1,1,-1,1,0,-1};

struct segtree_ele{
    int l,r,lrange,rrange,gt;
} segtree[4000009];

string s;
int a[2000009],pre[2000009],suf[2000009],n,i,q,l,r;

segtree_ele combine(int rl,int rr,segtree_ele l,segtree_ele r) {
    segtree_ele kq;
    kq.l=l.l;
    kq.r=r.r;
    kq.lrange=l.lrange;
    kq.rrange=r.rrange;
    int mid=(rr+rl)/2;
    if (l.lrange==mid-rl+1) {
        if (r.l>0) {
            kq.l+=r.l;
            kq.lrange+=r.lrange;
        }
    }
    if (r.rrange==rr-mid) {
        if (l.r>0) {
            kq.r+=l.r;
            kq.rrange+=l.rrange;
        }
    }
    kq.gt=max(max(l.gt,r.gt),l.r+r.l);
    return kq;
}

void init(int id,int l,int r) {
    if (l!=r) {
        int mid=(r+l)/2;
        init(id*2,l,mid);
        init(id*2+1,mid+1,r);
        segtree[id]=combine(l,r,segtree[id*2],segtree[id*2+1]);
    }
    else {
        segtree[id].l=a[l];
        segtree[id].r=a[l];
        segtree[id].gt=a[l];
        segtree[id].lrange=1;
        segtree[id].rrange=1;
    }
    //cout<<l<<' '<<r<<' '<<segtree[id].gt<<'\n';
}

segtree_ele get(int id,int l,int r,int u,int v) {
    if (l>r||r<u||l>v) {
        return {0,0,0,0,0};
    }
    if (u<=l&&r<=v) {
        return segtree[id];
    }
    int mid=(r+l)/2;
    return combine(l,r,get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}

int main(){
    IO;
    cin>>n;
    cin>>s;
    s=" "+s;
    for (i=1;i<=n;i++) {
        if (s[i]=='C') {
            a[i]=1;
        }
        else {
            a[i]=-1;
        }
    }
    init(1,1,n);
    for (i=1;i<=n;i++) {
        pre[i]=pre[i-1];
        if (s[i]=='C') {
            pre[i]++;
        }
        else {
            pre[i]--;
        }
    }
    for (i=n;i>=1;i--) {
        suf[i]=suf[i+1];
        if (s[i]=='C') {
            suf[i]++;
        }
        else {
            suf[i]--;
        }
    }
    cin>>q;
    for (i=1;i<=q;i++) {
        cin>>l>>r;
        //cout<<get(1,1,n,l,r).gt<<' ';
        cout<<-(pre[n]-pre[l-1]-suf[r+1]-max(0,get(1,1,n,l,r).gt))<<'\n';
    }
}

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