oj.uz

Submission #435088

# Submission time Handle Problem Language Result Execution time Memory
435088 2021-06-23T00:34:41 Z Mamnoon_Siam Distributing Candies (IOI21_candies) C++17
29 / 100
 938 ms 276784 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
  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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 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

# Verdict Execution time Memory Grader output
1 Runtime error 107 ms 13160 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 412 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 375 ms 50896 KB Output is correct
4 Correct 308 ms 93532 KB Output is correct
5 Correct 424 ms 48408 KB Output is correct
6 Correct 667 ms 127496 KB Output is correct
7 Correct 938 ms 276784 KB Output is correct
8 Correct 394 ms 48188 KB Output is correct
9 Correct 595 ms 255984 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1 ms 332 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -