oj.uz

Submission #654687

# Submission time Handle Problem Language Result Execution time Memory
654687 2022-11-01T09:01:44 Z Valera_Grinenko Election (BOI18_election) C++17
28 / 100
 3000 ms 1416 KB 
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
  int n, q;
  cin >> n;
  string s; cin >> s;
  cin >> q;
  while(q--) {
    vector<int> done(n);
    int l, r;
    cin >> l >> r; l--; r--;
    int pref = 0;
    int ans = 0;
    for(int i = l; i <= r; i++) {
      if(s[i] == 'C') pref++;
      else {
        if(!pref) { done[i] = 1; ans++; }
        else pref--;
      }
    }
    int mn_pref = 0; pref = 0;
    for(int i = r; i >= l; i--)
      if(!done[i]) {
        if(s[i] == 'C') pref++;
        else {
          pref--;
          mn_pref = min(mn_pref, pref);
        }
      }
    cout << ans - mn_pref << '\n';
  }
}
int main() {

  ios::sync_with_stdio(0); cin.tie(0);

  int t = 1;

  // cin >> t;

  while(t--) solve();

  return 0;
}
/*

*/

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 7 ms 336 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 7 ms 336 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Execution timed out 3079 ms 1416 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 7 ms 336 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Execution timed out 3079 ms 1416 KB Time limit exceeded
7 Halted 0 ms 0 KB -