제출 #435083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435083		Mamnoon_Siam	사탕 분배 (IOI21_candies)	C++17	0 / 100	107 ms	13152 KiB

candies

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

#define INPUT "01.in"

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

struct Node {
  Node *l = 0, *r = 0;
  int lo, hi;
  int m = -1, b = 0; // f : [lo, hi] --> y, f(x) = mx + b
  Node(int _lo, int _hi) : lo(_lo), hi(_hi) {

  }
  void upd_set(int _m, int _b) {
    m = _m, b = _b;
  }
  void upd_add(int _b) {
    b += _b;
  }
  void push() {
    if(lo < hi) {
      int mid = (lo + hi) >> 1;
      if(!l) l = new Node(lo, mid);
      if(!r) r = new Node(mid+1, hi);
      if(~m) {
        l -> upd_set(m, b);
        r -> upd_set(m, b);
      } else {
        l -> upd_add(b);
        r -> upd_add(b);
      }
    }
    m = -1, b = 0;
  }
  int query(int x) {
    if(lo == hi) {
      assert(~m);
      return m * x + b;
    }
    push();
    if(x <= l -> hi) {
      return l -> query(x);
    } else {
      return r -> query(x);
    }
  }
  void set_range(int L, int R, int mm, int bb) {
    if(lo > R or hi < L) {
      return;
    }
    if(L <= lo and hi <= R) {
      upd_set(mm, bb);
    } else {
      push();
      l -> set_range(L, R, mm, bb);
      r -> set_range(L, R, mm, bb);
    }
  }
  void add_range(int L, int R, int bb) {
    if(lo > R or hi < L) return;
    if(L <= lo and hi <= R) {
      upd_add(bb);
    } else {
      push();
      l -> add_range(L, R, bb);
      r -> add_range(L, R, bb);
    }
  }
};

const int lim = 15;

vi distribute_candies(vi c, vi l, vi r, vi v) {
  int n = sz(c), m = sz(v);
  assert(l[0] == 0 and *min_element(all(l)) == *max_element(all(l)));
  assert(r[0] == n-1 and *min_element(all(r)) == *max_element(all(r)));
  Node *tr = new Node(0, lim);
  tr -> set_range(0, lim, 0, 0);
  for(int i = 0; i < m; ++i) {
    tr -> add_range(0, lim, v[i]);
    if(v[i] > 0) {
      int lo = 0, hi = lim, opt = -1, mid;
      while(lo <= hi) {
        mid = (lo + hi) >> 1;
        if(tr -> query(mid) >= mid) {
          opt = mid;
          lo = mid+1;
        } else {
          hi = mid-1;
        }
      }
      tr -> set_range(0, opt, 1, 0);
    } else {
      int lo = 0, hi = lim, opt = -1, mid;
      while(lo <= hi) {
        mid = (lo + hi) >> 1;
        if(tr -> query(mid) <= 0) {
          opt = mid;
          lo = mid+1;
        } else {
          hi = mid-1;
        }
      }
      tr -> set_range(0, opt, 0, 0);
    }
  }
  vi a(n);
  for(int i = 0; i < n; ++i) {
    a[i] = tr -> query(c[i]);
  }
  return a;
}

#ifdef LOCAL
int main() {
  freopen(INPUT, "r", stdin);
  int n;
  assert(1 == scanf("%d", &n));
  std::vector<int> c(n);
  for(int i = 0; i < n; ++i) {
    assert(scanf("%d", &c[i]) == 1);
  }

  int q;
  assert(1 == scanf("%d", &q));
  std::vector<int> l(q), r(q), v(q);
  for(int i = 0; i < q; ++i) {
    assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
  }

  std::vector<int> ans = distribute_candies(c, l, r, v);

  for(int i = 0; i < n; ++i) {
    if (i > 0) {
      printf(" ");
    }
    printf("%d", ans[i]);
  }
  printf("\n");
  fclose(stdout);
  return 0;
}
#endif

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33