oj.uz

Submission #96315

# Submission time Handle Problem Language Result Execution time Memory
96315 2019-02-08T10:34:04 Z MrTEK Growing Trees (BOI11_grow) C++14
100 / 100
 555 ms 4728 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5 + 5;

int n,m,a[N],tree[N << 2],lazy[N << 2],dsa;

int init(int ind,int l,int r) {
  if (l == r)
    return tree[ind] = a[l];
  int mid = (l + r) / 2;
  return tree[ind] = init(ind + ind,l,mid) + init(ind + ind + 1,mid + 1,r);
}

void update(int ind,int l,int r,int lw,int rw,int val) {
  if (l > rw || r < lw || l > r)
    return ;
  if (l >= lw && r <= rw) {
    lazy[ind] += val;
    return;
  }
  int mid = (l + r) / 2;
  update(ind + ind,l,mid,lw,rw,val);
  update(ind + ind + 1,mid + 1,r,lw,rw,val);
}

void query(int ind,int l,int r,int w) {
  if (l > w || r < w)
    return;
  dsa += lazy[ind];
  if (l == w && r == w) {
    dsa += tree[ind];
    return;
  }
  int mid = (l + r) / 2;
  query(ind + ind,l,mid,w);
  query(ind + ind + 1,mid + 1,r,w);
}

int query(int w) {
  dsa = 0;
  query(1,1,n,w);
  return dsa;
}

int find1(int mn) {
  if (query(n) < mn)
    return -1;
  int l = 1 ,r = n;
  while(l < r) {
    int mid = (l + r - 1) / 2;
    if (query(mid) >= mn)
      r = mid;
    else
      l = mid + 1;
  }
  return r;
}

int find2(int mx) {
  if (query(1) > mx)
    return -1;
  int l = 1 ,r = n;
  while(l < r) {
    int mid = (l + r + 1) / 2;
    if (query(mid) <= mx)
      l = mid;
    else
      r = mid - 1;
  } 
  return l;
}

ii find3(int x) {
  return {find1(x),find2(x)};
}

void print() {
  cerr << "DIZININ SUANKI HALI::\n\n";
  for (int i = 1 ; i <= n ; i++)
    cerr << query(i) << " ";
  cerr << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  // freopen("input.gir","r",stdin);
  // freopen("output.cik","w",stdout);
  cin >> n >> m;
  for (int i = 1 ; i <= n ; i++)
    cin >> a[i];
  sort(a + 1, a + n + 1);
  init(1,1,n);
  while(m--) {
    char typ;
    cin >> typ;
    if (typ == 'F') {
      int c,h;
      cin >> c >> h;
      int l = find1(h) ,r = l + c - 1;
      if (l == -1)
        continue;
      if (r >= n)
        update(1,1,n,l,n,1);
      else {
        int tut = query(r);
        auto temp = find3(tut);
        update(1,1,n,l,temp.first - 1,1);
        int dis = r - temp.first + 1;
        update(1,1,n,temp.second - dis + 1,temp.second,1);
      }
    }
    else {
      int mn,mx;
      cin >> mn >> mx;
      int l = find1(mn) , r = find2(mx);
      if (l == -1 || r == -1)
        cout << 0 << "\n";
      else
        cout << r - l + 1 << "\n";
    }
    // print()
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 3420 KB Output is correct
2 Correct 482 ms 4692 KB Output is correct
3 Correct 150 ms 4472 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 8 ms 504 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 6 ms 552 KB Output is correct
5 Correct 194 ms 1784 KB Output is correct
6 Correct 239 ms 1784 KB Output is correct
7 Correct 15 ms 632 KB Output is correct
8 Correct 98 ms 1280 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 1432 KB Output is correct
2 Correct 214 ms 1912 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 127 ms 1644 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 1572 KB Output is correct
2 Correct 249 ms 1784 KB Output is correct
3 Correct 26 ms 632 KB Output is correct
4 Correct 226 ms 2036 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 2540 KB Output is correct
2 Correct 421 ms 4168 KB Output is correct
3 Correct 70 ms 1400 KB Output is correct
4 Correct 141 ms 4240 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 3576 KB Output is correct
2 Correct 422 ms 3524 KB Output is correct
3 Correct 137 ms 4348 KB Output is correct
4 Correct 59 ms 1272 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 3680 KB Output is correct
2 Correct 296 ms 4188 KB Output is correct
3 Correct 138 ms 4552 KB Output is correct
4 Correct 56 ms 1336 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 3400 KB Output is correct
2 Correct 423 ms 3516 KB Output is correct
3 Correct 71 ms 3448 KB Output is correct
4 Correct 259 ms 3832 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 3720 KB Output is correct
2 Correct 438 ms 4400 KB Output is correct
3 Correct 555 ms 4728 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 3912 KB Output is correct