Submission #435088

#	Time	Username	Problem	Language	Result	Execution time	Memory
435088		Mamnoon_Siam	Distributing Candies (IOI21_candies)	C++17	29 / 100	938 ms	276784 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
  int y_mx = 0, y_mn = 0;
  Node(int _lo, int _hi) : lo(_lo), hi(_hi) {

  }
  void upd_set(int _m, int _b) {
    m = _m, b = _b;
    y_mx = m * hi + b;
    y_mn = m * lo + b;
  }
  void upd_add(int _b) {
    b += _b;
    y_mx += _b;
    y_mn += _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);
    }
    y_mx = r -> y_mx;
    y_mn = l -> y_mn;
  }
  int get_cap() {
    if(lo == hi) return lo;
    push();
    if(r -> y_mn >= r -> lo) {
      return r -> get_cap();
    } else {
      return l -> get_cap();
    }
  }
  int get_cup() {
    if(lo == hi) return lo;
    push();
    if(r -> y_mn <= 0) {
      return r -> get_cup();
    } else {
      return l -> get_cup();
    }
  }
  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);
      y_mx = r -> y_mx;
      y_mn = l -> y_mn;
    }
  }
  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);
      y_mx = r -> y_mx;
      y_mn = l -> y_mn;
    }
  }
};

const int lim = 1000000000;

vi distribute_candies(vi c, vi l, vi r, vi v) {
  cerr << sizeof(Node) << endl;
  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 opt = tr -> get_cap();
      tr -> set_range(0, opt, 1, 0);
    } else {
      int opt = tr -> get_cup();
      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: 29 / 29
• Subtask 5: 0 / 33