[BOJ] 2243번 사탕상자

문제 바로가기

접근

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1000000;

int N, A, B, C, h;
int *tree;

int query(int node, int start, int end, int seq) {
  if(start == end)
    return start;

  if(tree[node * 2] >= seq)
    return query(node * 2, start, (start + end) / 2, seq);
  else
    return query(node * 2 + 1, (start + end) / 2 + 1, end, seq - tree[node * 2]);
}

void update(int node, int start, int end, int idx, int diff) {
  if(idx < start || idx > end)
    return;

  tree[node] += diff;
  if(start != end) {
    update(node * 2, start, (start + end) / 2, idx, diff);
    update(node * 2 + 1, (start + end) / 2 + 1, end, idx, diff);
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  cin >> N;
  h = ceil(log2(MAX));
  tree = new int[1 << (h + 1)];
  memset(tree, 0, sizeof(*tree));

  for(int i = 0; i < N; i++) {
    cin >> A;
    if(A == 1) {
      cin >> B;
      int ans = query(1, 1, MAX, B);
      cout << ans << "\n";
      update(1, 1, MAX, ans, -1);
    }
    else {
      cin >> B >> C;
      update(1, 1, MAX, B, C);
    }
  }
}