Submission #860361

#	Time	Username	Problem	Language	Result	Execution time	Memory
860361		Markynoodle	Election (BOI18_election)	C++17	28 / 100	3040 ms	1676 KiB

election

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

#define all(x) x.begin(),x.end()
#define ll long long
#define fastOI ios_base::sync_with_stdio(false); cin.tie(nullptr);
auto cmp = [](int a, int b){return a > b;};
auto cmp1 = [](pair<ll,ll> a, pair<ll,ll> b){return a.second < b.second;};
ll mod = 1000000007;


int main(){
    fastOI
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int> vals(n, 0);
    vector<int> prefix(n+1, 0);
    for(int i =0; i<n; i++){
        if(s[i] == 'T')vals[i] = -1;
        else vals[i] = 1;
        if(vals[i] == 1)prefix[i+1]++;
        else prefix[i+1]--;
        prefix[i+1] += prefix[i];
    }
    int q;
    cin>>q;
    for(int i = 0; i<q; i++){
        int l, r;
        cin>>l>>r;
        int sol = 0;
        int dif = prefix[r] - prefix[l-1];
        unordered_set<int> used;
        int cur = 0;
        for(int j = l-1; j<r; j++){
            if(vals[j] == -1){
                if(cur > 0)cur--;
                else{
                    used.insert(j);
                }
            }
            else cur++;
        }
        cur = 0;
        for(int j = r-1; j+1>=l; j--){
            if(used.count(j))continue;
            if(vals[j] == -1){
                if(cur > 0)cur--;
                else{
                    used.insert(j);
                }
            }
            else cur++;
        }
        sol = used.size();
        cout<<sol<<"\n";

    }
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:33:13: warning: unused variable 'dif' [-Wunused-variable]
   33 |         int dif = prefix[r] - prefix[l-1];
      |             ^~~

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