oj.uz

Submission #860361

# Submission time Handle Problem Language Result Execution time Memory
860361 2023-10-12T17:52:57 Z Markynoodle Election (BOI18_election) C++17
28 / 100
 3000 ms 1676 KB 
#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

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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 348 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 14 ms 348 KB Output is correct
4 Correct 32 ms 348 KB Output is correct
5 Correct 22 ms 348 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 348 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 14 ms 348 KB Output is correct
4 Correct 32 ms 348 KB Output is correct
5 Correct 22 ms 348 KB Output is correct
6 Execution timed out 3040 ms 1676 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 348 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 14 ms 348 KB Output is correct
4 Correct 32 ms 348 KB Output is correct
5 Correct 22 ms 348 KB Output is correct
6 Execution timed out 3040 ms 1676 KB Time limit exceeded
7 Halted 0 ms 0 KB -