oj.uz

Submission #96313

# Submission time Handle Problem Language Result Execution time Memory
96313 2019-02-08T10:22:21 Z MrTEK Growing Trees (BOI11_grow) C++14
10 / 100
 546 ms 5752 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

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;
}

pair <int,int> 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;
}

main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  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)
        cout << 0 << "\n";
      else
        cout << r - l + 1 << "\n";
    }
    // print()
  }
}

Compilation message

grow.cpp:88:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 309 ms 5752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 476 KB Output is correct
2 Incorrect 9 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 177 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 306 ms 3256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 5276 KB Output is correct
2 Incorrect 428 ms 5368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 331 ms 5256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 5380 KB Output is correct
2 Incorrect 449 ms 5256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 426 ms 5508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 5752 KB Output is correct