oj.uz

Submission #103925

# Submission time Handle Problem Language Result Execution time Memory
103925 2019-04-03T09:37:38 Z MrTEK Election (BOI18_election) C++14
82 / 100
 135 ms 8468 KB 
#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.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2816 KB Output is correct
2 Correct 7 ms 2816 KB Output is correct
3 Correct 7 ms 2944 KB Output is correct
4 Correct 9 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 117 ms 8028 KB Output is correct
7 Correct 78 ms 7676 KB Output is correct
8 Correct 95 ms 7672 KB Output is correct
9 Correct 113 ms 8028 KB Output is correct
10 Correct 112 ms 8080 KB Output is correct
11 Correct 134 ms 8468 KB Output is correct
12 Correct 130 ms 8328 KB Output is correct
13 Correct 115 ms 8444 KB Output is correct
14 Correct 115 ms 8184 KB Output is correct
15 Correct 135 ms 8200 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2816 KB Output is correct
2 Correct 7 ms 2816 KB Output is correct
3 Correct 7 ms 2944 KB Output is correct
4 Correct 9 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 117 ms 8028 KB Output is correct
7 Correct 78 ms 7676 KB Output is correct
8 Correct 95 ms 7672 KB Output is correct
9 Correct 113 ms 8028 KB Output is correct
10 Correct 112 ms 8080 KB Output is correct
11 Correct 134 ms 8468 KB Output is correct
12 Correct 130 ms 8328 KB Output is correct
13 Correct 115 ms 8444 KB Output is correct
14 Correct 115 ms 8184 KB Output is correct
15 Correct 135 ms 8200 KB Output is correct
16 Runtime error 18 ms 6908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -