Submission #469683

#	Time	Username	Problem	Language	Result	Execution time	Memory
469683		MohamedFaresNebili	Election (BOI18_election)	C++14	28 / 100	3067 ms	1528 KiB

election

#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using ld  = long double;

#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()

const ll MOD = 998244353;
const long double EPS = 0.000000001;
const double PI = 3.14159265358979323846;
const int nx[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
const int ny[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

ll n, q, arr[500005];

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    string s; cin>>n>>s>>q;
    while(q--) {
        ll a, b; cin>>a>>b; a--; b--;
        ll cap=0, tony=0; int vis[n];
        memset(vis, 0, sizeof vis);
        for(int i=a;i<=b;i++) {
            if(s[i]=='C') cap++;
            if(s[i]=='T') {
                tony++;
                if(tony>cap) {
                    vis[i]=1; tony--;
                }
            }
        }
        cap=0, tony=0; ll ans=0;
        for(int i=b;i>=a;i--) {
            if(s[i]=='C') cap++;
            if(s[i]=='T'&&!vis[i]) {
                tony++;
                if(tony>cap) {
                    vis[i]=1; tony--;
                }
            }
        }
        for(int i=a;i<=b;i++)
            if(vis[i]) ans++;
        cout<<ans<<'\n';
    }
    return 0;
}

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