답안 #96315 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96315	2019-02-08T10:34:04 Z	MrTEK	Growing Trees (BOI11_grow)	C++14	100 / 100	555 ms	4728 KB

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.0 / 10.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	395 ms	3912 KB	Output is correct

답안 #96315

Compilation message