Submission #1133893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133893		ByeWorld	Election (BOI18_election)	C++20	28 / 100	3093 ms	1956 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 = 2e5+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];
int day, tag[MAXN];

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;
    while(q--){
        int l,r;cin>>l>>r;
        int tot = 0, ans = 0; day++;
        for(int i=l;i<=r;i++){
            if(tot==0 && a[i]==-1){
                tag[i] = day; ans++;
            } else tot += a[i];
        }
        tot = 0; int mn = 0;
        for(int i=r; i>=l; i--){
            if(tag[i]==day) continue;
            tot += a[i]; mn = min(mn, tot);
        }
        cout << ans-mn << '\n';
    }
}

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