Submission #810442

#	Time	Username	Problem	Language	Result	Execution time	Memory
810442		WLZ	Distributing Candies (IOI21_candies)	C++17	27 / 100	746 ms	113304 KiB

candies

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

using ll = long long;

const ll LINF = (ll) 1e18;
const int SZ = (1 << 22);

ll mx[SZ], mn[SZ], lazy_add[SZ];

void push_add(int idx) {
  if (lazy_add[idx] == 0) return;
  mx[idx] += lazy_add[idx]; mn[idx] += lazy_add[idx];
  if (2 * idx + 1 < SZ) {
    lazy_add[2 * idx] += lazy_add[idx];
    lazy_add[2 * idx + 1] += lazy_add[idx];
  }
  lazy_add[idx] = 0;
}

void add(int idx, int cl, int cr, int l, int r, int val) {
  push_add(idx);
  if (cl > r || cr < l) return;
  if (l <= cl && cr <= r) {
    lazy_add[idx] += val;
    push_add(idx);
    return;
  }
  int mid = (cl + cr) / 2;
  add(2 * idx, cl, mid, l, r, val); add(2 * idx + 1, mid + 1, cr, l, r, val);
  mx[idx] = max(mx[2 * idx], mx[2 * idx + 1]);
  mn[idx] = min(mn[2 * idx], mn[2 * idx + 1]);
}

void max_eq(int idx, int cl, int cr, int l, int r, ll val) {
  push_add(idx);
  if (cl > r || cr < l || mn[idx] >= val) return;
  if (l <= cl && cr <= r && mx[idx] < val) add(idx, cl, cr, l, r, val - mx[idx]);
  int mid = (cl + cr) / 2;
  max_eq(2 * idx, cl, mid, l, r, val); max_eq(2 * idx + 1, mid + 1, cr, l, r, val);
  mx[idx] = max(mx[2 * idx], mx[2 * idx + 1]);
  mn[idx] = min(mn[2 * idx], mn[2 * idx + 1]);
}

void min_eq(int idx, int cl, int cr, int l, int r, ll val) {
  push_add(idx);
  if (cl > r || cr < l || mx[idx] <= val) return;
  if (l <= cl && cr <= r && mn[idx] > val) add(idx, cl, cr, l, r, val - mn[idx]);
  int mid = (cl + cr) / 2;
  min_eq(2 * idx, cl, mid, l, r, val); min_eq(2 * idx + 1, mid + 1, cr, l, r, val);
  mx[idx] = max(mx[2 * idx], mx[2 * idx + 1]);
  mn[idx] = min(mn[2 * idx], mn[2 * idx + 1]);
}

vector<int> ans;

void calc_ans(int idx, int cl, int cr) {
  push_add(idx);
  if (cl == cr) {
    ans[cl] = mx[idx];
    return;
  }
  int mid = (cl + cr) / 2;
  calc_ans(2 * idx, cl, mid);
  calc_ans(2 * idx + 1, mid + 1, cr);
}

int n, q;

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(), q = (int) l.size();
  memset(mx, 0, sizeof mx);
  memset(mn, 0, sizeof mn);
  memset(lazy_add, 0, sizeof lazy_add);
  for (int i = 0; i < q; i++) {
    add(1, 0, n - 1, l[i], r[i], v[i]);
    max_eq(1, 0, n - 1, 0, n - 1, 0);
    min_eq(1, 0, n - 1, 0, n - 1, c[0]);
  }
  ans.resize(n);
  calc_ans(1, 0, n - 1);
  return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33