제출 #813049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
813049		WLZ	Distributing Candies (IOI21_candies)	C++17	37 / 100	621 ms	43564 KiB

candies

#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) {
  if (cur->l == cur->r) return cur->l;
  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]);
      }
      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: 0 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33