Submission #584349

#	Time	Username	Problem	Language	Result	Execution time	Memory
584349		radal	Election (BOI18_election)	C++17	0 / 100	4 ms	340 KiB

election

#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,sse4,avx2")
//#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e5+20,mod = 1e9+7,inf = 1e9+10,base = 233;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
int ps[N],cal[N];
bool go[N];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int n,q;
    string s;
    cin >> n >> s >> q;
    s = '#'+s;
    rep(i,1,n+1){
        if (s[i] == 'C') ps[i] = ps[i-1]+1;
        else ps[i] = ps[i-1]-1;
    }
    while (q--){
        int l,r;
        cin >> l >> r;
        cal[l-1] = 0;
        int mx = 0;
        rep(i,l,r+1){
            go[i] = 0;
            if (ps[l-1]-ps[i] > mx || i == l) go[i] = 1;
            mx = max(mx,ps[l-1]-ps[i]);
            cal[i] = mx;
        }
        int ans = 0;
        mx = 0;
        repr(i,r,l){
            mx = max(mx,-ps[r]+ps[i-1]);
            if (!go[i]) continue;
            ans = max(ans,mx+cal[i-1]);
        }
        cout << ans << endl;
    }
    return 0;
}

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