oj.uz

답안 #96311

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96311 2019-02-08T10:01:41 Z MrTEK Growing Trees (BOI11_grow) C++14
10 / 100
 459 ms 5184 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);
  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()
  }
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 289 ms 4448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Incorrect 7 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 199 ms 1816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 176 ms 2012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 286 ms 2812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 3848 KB Output is correct
2 Incorrect 432 ms 4488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 307 ms 4080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 459 ms 4608 KB Output is correct
2 Incorrect 438 ms 4112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 396 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

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