Submission #1165537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165537		fryingduc	Distributing Candies (IOI21_candies)	C++20	100 / 100	264 ms	39112 KiB

candies

#include "candies.h"

#include <vector>
#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n, q;
vector<pair<int, int>> ev[maxn];
int c[maxn];

struct node {
  long long sum;
  long long mn;
  long long mx;
  
  node() { sum = mn = mx = 0; }
  
  node(long long sum, long long mn, long long mx) : sum(sum), mn(mn), mx(mx) {}
  
  node operator+(const node &o) const {
    node res = *this;
    res.mx = max(res.mx, res.sum + o.mx);
    res.mn = min(res.mn, res.sum + o.mn);
    res.sum += o.sum;
    return res;
  }
} tree[maxn << 2];

void update(int pos, int val, int ind = 1, int l = 1, int r = q) {
  if (l == r) {
    tree[ind].sum += val;
    tree[ind].mn = min(0ll, tree[ind].sum);
    tree[ind].mx = max(0ll, tree[ind].sum);
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid) update(pos, val, ind << 1, l, mid);
  else update(pos, val, ind << 1 | 1, mid + 1, r);
  tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
}

node get(int x, int y, int ind = 1, int l = 1, int r = q) {
  if (l > y || r < x) return node();
  if (x <= l and r <= y) {
    return tree[ind];
  }
  int mid = (l + r) >> 1;
  return get(x, y, ind << 1, l, mid) + get(x, y, ind << 1 | 1, mid + 1, r);
}

int walk(int k, int ind = 1, int l = 1, int r = q) {
  if (l == r) {
    if (tree[ind].sum > k) return k;
    if (tree[ind].sum < 0) return 0;
    return tree[ind].sum;
  }
  int mid = (l + r) >> 1;
  if (tree[ind << 1 | 1].mx - tree[ind << 1 | 1].mn > k) {
    return walk(k, ind << 1 | 1, mid + 1, r);
  }
  int cur = walk(k, ind << 1, l, mid);
  if (cur + tree[ind << 1 | 1].mn < 0) {
    return tree[ind << 1 | 1].sum - tree[ind << 1 | 1].mn;
  }
  if (cur + tree[ind << 1 | 1].mx > k) {
    return k - (tree[ind << 1 | 1].mx - tree[ind << 1 | 1].sum);
  }
  return cur + tree[ind << 1 | 1].sum;
}

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
  n = (int)C.size();
  q = (int)L.size();
  for (int i = 0; i < n; ++i) {
    c[i + 1] = C[i];
  }
  for (int i = 0; i < q; ++i) {
    int l = L[i], r = R[i], v = V[i];
    ++l, ++r;
    ev[l].emplace_back(v, i + 1);
    if (r < n) {
      ev[r + 1].emplace_back(-v, i + 1);
    }
  }
  vector<int> res;
  for (int i = 1; i <= n; ++i) {
    for (auto [v, id] : ev[i]) {
      update(id, v); 
    }
    res.push_back(walk(c[i]));      
  }
  debug(res);
  return res;
}

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