oj.uz

Submission #103927

# Submission time Handle Problem Language Result Execution time Memory
103927 2019-04-03T09:38:26 Z MrTEK Election (BOI18_election) C++14
100 / 100
 1054 ms 44836 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int N = 5e5 + 5;

vector <int> v;
vector <ii> del[N];
int n,m,q,ans[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) {
    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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12160 KB Output is correct
2 Correct 13 ms 12160 KB Output is correct
3 Correct 13 ms 12160 KB Output is correct
4 Correct 15 ms 12160 KB Output is correct
5 Correct 17 ms 12160 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12160 KB Output is correct
2 Correct 13 ms 12160 KB Output is correct
3 Correct 13 ms 12160 KB Output is correct
4 Correct 15 ms 12160 KB Output is correct
5 Correct 17 ms 12160 KB Output is correct
6 Correct 118 ms 16196 KB Output is correct
7 Correct 91 ms 15864 KB Output is correct
8 Correct 99 ms 15804 KB Output is correct
9 Correct 115 ms 16108 KB Output is correct
10 Correct 105 ms 16120 KB Output is correct
11 Correct 110 ms 16452 KB Output is correct
12 Correct 127 ms 16364 KB Output is correct
13 Correct 112 ms 16632 KB Output is correct
14 Correct 115 ms 16336 KB Output is correct
15 Correct 98 ms 16276 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12160 KB Output is correct
2 Correct 13 ms 12160 KB Output is correct
3 Correct 13 ms 12160 KB Output is correct
4 Correct 15 ms 12160 KB Output is correct
5 Correct 17 ms 12160 KB Output is correct
6 Correct 118 ms 16196 KB Output is correct
7 Correct 91 ms 15864 KB Output is correct
8 Correct 99 ms 15804 KB Output is correct
9 Correct 115 ms 16108 KB Output is correct
10 Correct 105 ms 16120 KB Output is correct
11 Correct 110 ms 16452 KB Output is correct
12 Correct 127 ms 16364 KB Output is correct
13 Correct 112 ms 16632 KB Output is correct
14 Correct 115 ms 16336 KB Output is correct
15 Correct 98 ms 16276 KB Output is correct
16 Correct 958 ms 42392 KB Output is correct
17 Correct 692 ms 38944 KB Output is correct
18 Correct 818 ms 40088 KB Output is correct
19 Correct 814 ms 41788 KB Output is correct
20 Correct 999 ms 42232 KB Output is correct
21 Correct 1054 ms 44408 KB Output is correct
22 Correct 963 ms 44024 KB Output is correct
23 Correct 1012 ms 44836 KB Output is correct
24 Correct 838 ms 44028 KB Output is correct
25 Correct 977 ms 43384 KB Output is correct