oj.uz

답안 #435084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
435084 2021-06-23T00:17:58 Z Mamnoon_Siam 사탕 분배 (IOI21_candies) C++17
0 / 100
 3005 ms 1048580 KB 
#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 = 1000000000;

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Runtime error 1 ms 332 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 106 ms 13060 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1484 ms 116556 KB Output is correct
4 Correct 268 ms 96424 KB Output is correct
5 Correct 1301 ms 48876 KB Output is correct
6 Correct 1779 ms 187660 KB Output is correct
7 Runtime error 3005 ms 1048580 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Runtime error 1 ms 332 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -