oj.uz

Submission #813101

# Submission time Handle Problem Language Result Execution time Memory
813101 2023-08-07T13:30:10 Z WLZ Distributing Candies (IOI21_candies) C++17
100 / 100
 638 ms 50176 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../../../debug.h"
#else
#define debug(...) 0
#endif
 
using ll = long long;
 
const int INF = 0x3f3f3f3f;
const ll LINF = (ll) 1e18;
 
int n, q;
 
struct node {
  int l, r;
  ll min, max;
  int min_idx, max_idx;
  ll lazy;
  node *left, *right;
};
 
node *build(int l, int r) {
  if (l == r) return new node{l, r, 0, 0, r, r, 0, nullptr, nullptr};
  node *left = build(l, (l + r) / 2), *right = build((l + r) / 2 + 1, r);
  return new node{l, r, 0, 0, r, r, 0, left, right};
}
 
void push(node *cur) {
  //debug(cur->l, cur->r);
  if (cur->lazy == 0) return;
  cur->min += cur->lazy; cur->max += cur->lazy;
  if (cur->left != nullptr) {
    cur->left->lazy += cur->lazy;
    cur->right->lazy += cur->lazy;
  }
  cur->lazy = 0;
}
 
void combine_children(node *cur) {
  if (cur->left == nullptr) return;
  cur->max = max(cur->left->max, cur->right->max);
  cur->min = min(cur->left->min, cur->right->min);
  cur->max_idx = (cur->left->max > cur->right->max ? cur->left->max_idx : cur->right->max_idx);
  cur->min_idx = (cur->left->min < cur->right->min ? cur->left->min_idx : cur->right->min_idx);
}
 
pair<ll, int> query_max(node *cur, int l, int r) {
  push(cur);
  if (cur->l > r || cur->r < l) return {-LINF, -1};
  if (l <= cur->l && cur->r <= r) return {cur->max, cur->max_idx};
  return max(query_max(cur->left, l, r), query_max(cur->right, l, r));
}
 
pair<ll, int> query_min(node *cur, int l, int r) {
  push(cur);
  if (cur->l > r || cur->r < l) return {LINF, +1};
  if (l <= cur->l && cur->r <= r) return {cur->min, -cur->min_idx};
  return min(query_min(cur->left, l, r), query_min(cur->right, l, r));
}
 
void update(node *cur, int l, int r, ll v) {
  push(cur);
  if (cur->l > r || cur->r < l) return;
  if (l <= cur->l && cur->r <= r) {
    cur->lazy += v;
    push(cur);
    return;
  }
  update(cur->left, l, r, v); update(cur->right, l, r, v);
  combine_children(cur);
}
 
int find(node *cur, ll c, ll rmx = -LINF, ll rmn = LINF) {
  push(cur);
  if (cur->l == cur->r) return cur->l;
  push(cur->left); push(cur->right);
  if (max(rmx, cur->right->max) - min(rmn, cur->right->min) < c) return find(cur->left, c, max(rmx, cur->right->max), min(rmn, cur->right->min));
  return find(cur->right, c, rmx, rmn);
}
 
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
  n = (int) c.size();
  l.insert(l.begin(), 0); l.insert(l.begin(), 0);
  r.insert(r.begin(), n - 1); r.insert(r.begin(), n - 1);
  v.insert(v.begin(), -INF); v.insert(v.begin(), +INF);
  q = (int) l.size();
  vector< vector<int> > a(n);
  for (int i = 0; i < q; i++) {
    a[l[i]].push_back(i + 1);
    if (r[i] < n - 1) a[r[i] + 1].push_back(i + 1);
  }
  node *root = build(0, q);
  vector<int> ans(n), in(q + 1, 0);
  for (int i = 0; i < n; i++) {
    for (auto &idx : a[i]) {
      if (in[idx]) {
        update(root, idx, q, -v[idx - 1]);
      } else {
        update(root, idx, q, +v[idx - 1]);
      }
      //for (int i = 0; i <= q; i++) cerr << query_max(root, i, i).first << ' ';
      //cerr << endl;
      in[idx] = !in[idx];
    }
    int k = find(root, c[i]);
    auto mn = query_min(root, k, q), mx = query_max(root, k, q), all = query_max(root, q, q);
    if (-mn.second > mx.second) ans[i] = all.first - mn.first;
    else ans[i] = c[i] + all.first - mx.first;
  }
  return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 4 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 43572 KB Output is correct
2 Correct 638 ms 43472 KB Output is correct
3 Correct 583 ms 43472 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 359 ms 32980 KB Output is correct
3 Correct 94 ms 7756 KB Output is correct
4 Correct 582 ms 43468 KB Output is correct
5 Correct 611 ms 49780 KB Output is correct
6 Correct 586 ms 50176 KB Output is correct
7 Correct 576 ms 49448 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 103 ms 31700 KB Output is correct
4 Correct 91 ms 7624 KB Output is correct
5 Correct 226 ms 38596 KB Output is correct
6 Correct 223 ms 38680 KB Output is correct
7 Correct 255 ms 38684 KB Output is correct
8 Correct 228 ms 38592 KB Output is correct
9 Correct 219 ms 38672 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 629 ms 43572 KB Output is correct
7 Correct 638 ms 43472 KB Output is correct
8 Correct 583 ms 43472 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 359 ms 32980 KB Output is correct
11 Correct 94 ms 7756 KB Output is correct
12 Correct 582 ms 43468 KB Output is correct
13 Correct 611 ms 49780 KB Output is correct
14 Correct 586 ms 50176 KB Output is correct
15 Correct 576 ms 49448 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 103 ms 31700 KB Output is correct
19 Correct 91 ms 7624 KB Output is correct
20 Correct 226 ms 38596 KB Output is correct
21 Correct 223 ms 38680 KB Output is correct
22 Correct 255 ms 38684 KB Output is correct
23 Correct 228 ms 38592 KB Output is correct
24 Correct 219 ms 38672 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 117 ms 8876 KB Output is correct
27 Correct 362 ms 35588 KB Output is correct
28 Correct 613 ms 48016 KB Output is correct
29 Correct 573 ms 48504 KB Output is correct
30 Correct 562 ms 48688 KB Output is correct
31 Correct 567 ms 48700 KB Output is correct
32 Correct 542 ms 49052 KB Output is correct