oj.uz

Submission #465769

# Submission time Handle Problem Language Result Execution time Memory
465769 2021-08-16T18:24:43 Z alexxela12345 Distributing Candies (IOI21_candies) C++17
100 / 100
 1047 ms 42912 KB 
#include "candies.h"

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

typedef long long ll;

mt19937 rd(179);

struct node {
  node *l, *r;

  int x, y;
  int val;
  int sz;
  ll sum;
  ll max_suf;
  ll min_suf;

  node(int x, int val) : x(x), val(val) {
    l = r = NULL;
    y = rd();
    sz = 1;
    sum = val;
    max_suf = max(0, val);
    min_suf = min(0, val);
  }
};

int get_sz(node *n) { return (n == NULL) ? 0 : n->sz; }

ll get_sum(node *n) { return (n == NULL) ? 0 : n->sum; }
ll get_max_suf(node *n) { return (n == NULL) ? 0 : n->max_suf; }
ll get_min_suf(node *n) { return (n == NULL) ? 0 : n->min_suf; }

int get_ct(node *n, int i) {
  if (i == get_sz(n->l)) {
    return n->val;
  }
  if (i < get_sz(n->l)) {
    return get_ct(n->l, i);
  }
  return get_ct(n->r, i - get_sz(n->l) - 1);
}

int getInd(node *n, int x) {
  if (n == NULL)
    return 0;
  if (x < n->x)
    return getInd(n->l, x);
  if (x == n->x)
    return get_sz(n->l);
  return getInd(n->r, x) + get_sz(n->l) + 1;
}

void pull(node *n) {
  n->sz = 1 + get_sz(n->l) + get_sz(n->r);
  n->sum = n->val + get_sum(n->l) + get_sum(n->r);
  n->min_suf = min(get_min_suf(n->r), get_sum(n->r) + n->val + get_min_suf(n->l));
  n->max_suf = max(get_max_suf(n->r), get_sum(n->r) + n->val + get_max_suf(n->l));
}

pair<node *, node *> split_sz(node *n, int k) {
  if (n == NULL)
    return {n, n};
  if (k <= get_sz(n->l)) {
    auto pp = split_sz(n->l, k);
    n->l = pp.second;
    pull(n);
    return {pp.first, n};
  }
  auto pp = split_sz(n->r, k - 1 - get_sz(n->l));
  n->r = pp.first;
  pull(n);
  return {n, pp.second};
}

node *merge(node *a, node *b) {
  if (a == NULL) {
    return b;
  }
  if (b == NULL)
    return a;
  if (a->y > b->y) {
    a->r = merge(a->r, b);
    pull(a);
    return a;
  }
  b->l = merge(a, b->l);
  pull(b);
  return b;
}

struct mdata {
  node *root = NULL;

  int size();
  int get(int);
};

int mdata::size() { return get_sz(root); }

int mdata::get(int i) { return get_ct(root, i); }

void erase(mdata &mda, int i, int x) {
  int ind = getInd(mda.root, i);
  auto pp1 = split_sz(mda.root, ind);
  auto pp2 = split_sz(pp1.second, 1);
  mda.root = merge(pp1.first, pp2.second);
}

void add(mdata &mda, int i, int x) {
  int ind = getInd(mda.root, i);
  auto pp = split_sz(mda.root, ind);
  mda.root = merge(merge(pp.first, new node(i, x)), pp.second);
}

int get_fst_diff(node *n, int mx_diff, ll mx, ll mn, ll cur) {
  if (n == NULL) {
    return 0;
  }
  ll mx1 = max(max(mx, get_sum(n->r) + n->val + cur), get_max_suf(n->r) + cur);
  ll mn1 = min(min(mn, get_sum(n->r) + n->val + cur), get_min_suf(n->r) + cur);
  if (mx1 - mn1 > mx_diff) {
    return get_fst_diff(n->r, mx_diff, mx, mn, cur) + 1 + get_sz(n->l);
  }
  return get_fst_diff(n->l, mx_diff, mx1, mn1, cur + get_sum(n->r) + n->val);
}

int get_fst_diff(mdata &mda, int mx_diff) {
  // returns index to first arrow after which everything contains in a segment
  // of size mx
  int ans = get_fst_diff(mda.root, mx_diff, 0, 0, 0);
  return ans;
  int cur = 0;
  int mn = 0, mx = 0;
  for (int i = mda.size() - 1; i >= 0; i--) {
    int a = mda.get(i);
    cur += a;
    mn = min(mn, cur);
    mx = max(mx, cur);
    if (mx - mn > mx_diff) {
      assert(ans == i + 1);
      return i + 1;
    }
  }
  assert(ans == 0);
  return 0;
}

int get_min_suf(mdata &mda, int fst) {
  auto pp = split_sz(mda.root, fst);
  int ans = get_min_suf(pp.second);
  mda.root = merge(pp.first, pp.second);
  return ans;
  int cur = 0;
  int mn = 0;
  for (int i = mda.size() - 1; i >= fst; i--) {
    cur += mda.get(i);
    if (cur < mn) {
      mn = cur;
    }
  }
  return mn;
}

int get_max_suf(mdata &mda, int fst) {
  auto pp = split_sz(mda.root, fst);
  int ans = get_max_suf(pp.second);
  mda.root = merge(pp.first, pp.second);
  return ans;
  int cur = 0;
  int mn = 0;
  for (int i = mda.size() - 1; i >= fst; i--) {
    cur += mda.get(i);
    if (cur > mn) {
      mn = cur;
    }
  }
  return mn;
}

int get_ans(mdata &mda, int mx) {
  int fst = get_fst_diff(mda, mx);
  int start = 0;
  if (fst == 0) {
    start = 0;
  } else {
    int a = mda.get(fst - 1);
    if (a > 0) {
      start = mx;
    } else {
      start = 0;
    }
  }
  if (start == 0) {
    int ans = get_max_suf(mda, fst);
    return start + ans;
  } else {
    int ans = get_min_suf(mda, fst);
    return start + ans;
  }
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r,
                               vector<int> v) {
  int n = c.size();
  vector<vector<int>> add_evs(n + 1), rem_evs(n + 1);
  for (int i = 0; i < (int)l.size(); i++) {
    add_evs[l[i]].push_back(i);
    rem_evs[r[i] + 1].push_back(i);
  }
  mdata mda;
  vector<int> ans;
  ans.reserve(n);
  for (int i = 0; i < n; i++) {
    for (int el : rem_evs[i]) {
      erase(mda, el, v[el]);
    }
    for (int el : add_evs[i]) {
      add(mda, el, v[el]);
    }
    ans.push_back(get_ans(mda, c[i]));
  }
  return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 5 ms 588 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 36388 KB Output is correct
2 Correct 1020 ms 38180 KB Output is correct
3 Correct 1047 ms 38136 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 669 ms 20052 KB Output is correct
3 Correct 111 ms 13992 KB Output is correct
4 Correct 938 ms 39604 KB Output is correct
5 Correct 990 ms 42768 KB Output is correct
6 Correct 935 ms 42912 KB Output is correct
7 Correct 922 ms 42564 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 135 ms 19216 KB Output is correct
4 Correct 96 ms 12104 KB Output is correct
5 Correct 279 ms 30836 KB Output is correct
6 Correct 279 ms 30940 KB Output is correct
7 Correct 246 ms 30884 KB Output is correct
8 Correct 271 ms 34196 KB Output is correct
9 Correct 242 ms 35632 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 985 ms 36388 KB Output is correct
7 Correct 1020 ms 38180 KB Output is correct
8 Correct 1047 ms 38136 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 669 ms 20052 KB Output is correct
11 Correct 111 ms 13992 KB Output is correct
12 Correct 938 ms 39604 KB Output is correct
13 Correct 990 ms 42768 KB Output is correct
14 Correct 935 ms 42912 KB Output is correct
15 Correct 922 ms 42564 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 135 ms 19216 KB Output is correct
19 Correct 96 ms 12104 KB Output is correct
20 Correct 279 ms 30836 KB Output is correct
21 Correct 279 ms 30940 KB Output is correct
22 Correct 246 ms 30884 KB Output is correct
23 Correct 271 ms 34196 KB Output is correct
24 Correct 242 ms 35632 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 98 ms 13516 KB Output is correct
27 Correct 610 ms 22736 KB Output is correct
28 Correct 1014 ms 40984 KB Output is correct
29 Correct 980 ms 41472 KB Output is correct
30 Correct 941 ms 41472 KB Output is correct
31 Correct 912 ms 41664 KB Output is correct
32 Correct 939 ms 41980 KB Output is correct