oj.uz

Submission #986825

# Submission time Handle Problem Language Result Execution time Memory
986825 2024-05-21T10:05:06 Z MercubytheFirst Election (BOI18_election) C++14
28 / 100
 3000 ms 1652 KB 
#include "bits/stdc++.h"
#define pb push_back
#define endl '\n'
#define fi first
#define se second
#define CDIV(a,b) (((a)+(b)-(1))/(b))
using ll = long long;
using ld = long double;
const ll inf = 1e9 + 37;
const ll mod = 1e9 + 7;
const ll N = 5e5 + 37;
const ld eps = 1e-9;
const ld PI = acos((ld)-1);
 

template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);
template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v);
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

inline void solve(){
  int n;
  string s;
  cin >> n >> s;
  int Q;
  cin >> Q;
  while(Q--) {
    int l, r;
    cin >> l >> r;
    string tmp = s.substr(l - 1, r - l + 1);
    // cout << tmp << ' ';
    int ans = 0, count = 0;
    for(char& c : tmp) {
      assert(count >= 0);
      if(c == 'C') {
        count++;
        continue;
      }
      if(c != 'C' and c != 'T') {
        continue;
      }
      if(count == 0) {
        c = 'X';
        ans++;
      }
      else {
        count--;
      }
    }
    reverse(tmp.begin(), tmp.end());
    count = 0;
    for(char& c : tmp) {
      assert(count >= 0);
      if(c == 'C') {
        count++;
        continue;
      }
      if(c != 'C' and c != 'T') {
        continue;
      }
      if(count == 0) {
        c = 'X';
        ans++;
      }
      else {
        count--;
      }
    }
    reverse(tmp.begin(), tmp.end());
    // cout << tmp << ' ';
    cout << ans << endl;
  }
}


 
signed main(){
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(NULL); 
  // signed t; cin >> t; while(t--)
    solve();
}

template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
  for(T& x : v)
    is >> x;
  return is;
}

template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
  os << "[";
  for(size_t i = 0; i + 1 < N; ++i) {
    os << a[i] << ", ";
  }
  if(N > 0)
    os << a[N - 1];
  os << "]";
  return os;
}

template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ") ";
  return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << '[';
  for(auto x : v)
    os << x << ", ";
  os << "] ";
  return os;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}
//
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 9 ms 348 KB Output is correct
3 Correct 8 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 4 ms 344 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 9 ms 348 KB Output is correct
3 Correct 8 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Execution timed out 3039 ms 1652 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 348 KB Output is correct
2 Correct 9 ms 348 KB Output is correct
3 Correct 8 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Execution timed out 3039 ms 1652 KB Time limit exceeded
7 Halted 0 ms 0 KB -