Submission #96315

#	Time	Username	Problem	Language	Result	Execution time	Memory
96315		MrTEK	Growing Trees (BOI11_grow)	C++14	100 / 100	555 ms	4728 KiB

grow

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10