oj.uz

Submission #106150

# Submission time Handle Problem Language Result Execution time Memory
106150 2019-04-16T21:00:02 Z xiaowuc1 Election (BOI18_election) C++14
0 / 100
 5 ms 512 KB 
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef vector<vector<ll>> matrix;

const int RAGETREE_SZ = 500005;
int ragetree[4 * RAGETREE_SZ];
int n;
string s;
int dp[RAGETREE_SZ];
int total[RAGETREE_SZ];

int query(int idx, int lhs, int rhs, int tl, int tr) {
  if(lhs >= tl && rhs <= tr) return ragetree[idx];
  int ret = 1e9;
  int mid = (lhs+rhs)/2;
  if(mid >= tl) ret = min(ret, query(2*idx, lhs, mid, tl, tr));
  if(mid+1 <= tr) ret = min(ret, query(2*idx+1, mid+1, rhs, tl, tr));
  return ret;
}
int query(int lhs, int rhs) {
  return query(1, 0, n, lhs, rhs);
}

void init(int idx, int lhs, int rhs) {
  if(lhs == rhs) {
    ragetree[idx] = dp[lhs];
  }
  else {
    int mid = (lhs+rhs)/2;
    init(2*idx, lhs, mid);
    init(2*idx+1, mid+1, rhs);
    ragetree[idx] = min(ragetree[2*idx], ragetree[2*idx+1]);
  }
}
void init() {
  init(1, 0, n);
}

int lhsQ[500005];
int rhsQ[500005];
int ret[500005];
void solve() {
  cin >> n >> s;
  for(int i = 0; i < n; i++) {
    total[i+1] = total[i];
    if(s[i] == 'T') total[i+1]++;
  }
  int q;
  cin >> q;
  for(int i = 0; i < q; i++) {
    cin >> lhsQ[i] >> rhsQ[i];
    lhsQ[i]--;
    ret[i] = 0;
  }
  for(int i = 0; i < n; i++) {
    dp[i+1] = dp[i];
    if(s[i] == 'C') dp[i+1]++;
    else dp[i+1]--;
  }
  init();
  for(int i = 0; i < q; i++) {
    ret[i] = max(ret[i], dp[lhsQ[i]] - query(lhsQ[i], rhsQ[i]));
  }
  dp[n] = 0;
  for(int i = n-1; i >= 0; i--) {
    dp[i] = dp[i+1];
    if(s[i] == 'C') dp[i]++;
    else dp[i]--;
  }
  init();
  for(int i = 0; i < q; i++) {
    ret[i] = max(ret[i], dp[rhsQ[i]] - query(lhsQ[i], rhsQ[i]));
  }
  for(int i = 0; i < q; i++) {
    cout << min(ret[i], total[rhsQ[i]] - total[lhsQ[i]]) << "\n";
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
	/*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
	*/
	solve();
}

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -