제출 #103925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103925		MrTEK	Election (BOI18_election)	C++14	82 / 100	135 ms	8468 KiB

election

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e5 + 5;
const int inf = 1e6;

vector <int> v;
vector <ii> del[N];
int n,m,q,ans[N],asd[N];
char s[N];

struct node {
  int sum,mnsuf;
  node operator + (node oth) {
    return {sum + oth.sum,min(oth.mnsuf,oth.sum + mnsuf)};
  }
}tree[N << 2];
  
void update(int ind,int l,int r,int w,int val) {
  if (l > w || r < w)
    return;
  if (l == w && r == w) {
    asd[w] = val;
    tree[ind] = {val,min(val,0)};
    return;
  }
  int mid = (l + r) / 2;
  update(ind + ind,l,mid,w,val);
  update(ind + ind + 1,mid + 1,r,w,val);
  tree[ind] = tree[ind + ind] + tree[ind + ind + 1];
}

node query(int ind,int l,int r,int lw,int rw) {
  if (l > rw || r < lw)
    return {0,0};
  if (l >= lw && r <= rw)
    return tree[ind];
  int mid = (l + r) / 2;
  return query(ind + ind,l,mid,lw,rw) + query(ind + ind + 1,mid + 1,r,lw,rw);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n;
  for (int i = 1 ; i <= n ; i++)
    cin >> s[i];
  cin >> q;
  for (int i = 1 ; i <= q ; i++) {
    int l,r;
    cin >> l >> r;
    del[l].push_back({r,i});
  }
  for (int i = 1 ; i <= n ; i++)
    update(1,1,n,i,1);
  for (int i = n ; i >= 1 ; i--) {
    if (s[i] == 'C') {
      if (v.empty() == false) {
        update(1,1,n,v.back(),-1);
        v.pop_back();
      }
    }
    else {
      update(1,1,n,i,0);
      v.push_back(i);
    }
    for (auto j : del[i])
      ans[j.second] = upper_bound(v.rbegin(),v.rend(),j.first) - v.rbegin() - query(1,1,n,i,j.first).mnsuf;
  }
  for (int i = 1 ; i <= q ; i++)
    cout << ans[i] << "\n";
}

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 0 / 18