Submission #106149

#	Time	Username	Problem	Language	Result	Execution time	Memory
106149		xiaowuc1	Election (BOI18_election)	C++14	0 / 100	3 ms	384 KiB

election

#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 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;
  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 << ret[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
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18