Submission #435792

#	Time	Username	Problem	Language	Result	Execution time	Memory
435792		bicsi	Distributing Candies (IOI21_candies)	C++17	38 / 100	3474 ms	1048580 KiB

candies

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

using namespace std;
using ll = long long;
const int bs = 256;

vector<int> distribute_candies(
    vector<int> c, vector<int> l,
    vector<int> r, vector<int> v) {
  int n = c.size();

  vector<int> f(n, 0), nf(n, 0);
  vector<vector<ll>> ops(n / bs + 1);
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  for (int i = 0; i < n; i += bs) {
    int j = min(i + bs, n);
    sort(order.begin() + i, order.begin() + j, [&](int a, int b) {
      return c[a] < c[b];
    });
  }
  vector<ll> stk;
  auto refresh = [&](int bi) {
    if (ops[bi].empty()) return;

    // cerr << "refresh: " << bi << endl;
    // cerr << "ops: ";
    // for (auto x : ops[bi]) cerr << x << " "; cerr << endl;
    stk.clear();
    stk.push_back(4e18);
    stk.push_back(2e18);
    for (auto delta : ops[bi]) {
      if (delta == 0) continue;
      if (delta > 0) {
        ll rem = delta, px = 0;
        while (true) {
          ll x = stk.back();
          if (x - px > rem) {
            stk.push_back(px + rem);
            stk.push_back(0);
            break;
          } 
          rem -= (x - px);
          stk.pop_back();
          px = stk.back();
          stk.pop_back();
        }
      } else {
        ll rem = -delta;
        while (true) {
          ll px = stk.back(); stk.pop_back();
          ll x = stk.back();
          if (x - px > rem) {
            stk.push_back(px + rem);
            stk.push_back(0);
            stk.push_back(0);
            break;
          }
          rem -= (x - px);
          stk.pop_back();
        }
      }
    }
    reverse(stk.begin(), stk.end());
    // cerr << "stk: "; for (auto x : stk) cerr << x << " "; cerr << endl;

    ll value = 0;
    int ptr = 0;
    for (int i = bi * bs; i < (bi + 1) * bs && i < n; ++i) {
      ll ci = c[order[i]];
      while (stk[ptr + 1] < ci) {
        if (ptr % 2 == 0)
          value += stk[ptr + 1] - stk[ptr];
        ++ptr;
      }
      if (ptr % 2 == 0) {
        nf[order[i]] = value + (ci - stk[ptr]);
      } else {
        nf[order[i]] = value;
      }
      // cerr << "  " << order[i] << " => " << nf[order[i]] << endl;
    }

    ll mind = 0, maxd = 0, nowd = 0;
    for (auto x : ops[bi]) {
      nowd += x;
      mind = min(mind, nowd);
      maxd = max(maxd, nowd);
    }

    for (int i = bi * bs; i < (bi + 1) * bs && i < n; ++i) {
      ll hi = min(c[i] - maxd, (ll)f[i]);
      ll lo = -mind;
      if (lo < hi) 
        nf[i] += hi - lo; 
    }


    for (int i = bi * bs; i < (bi + 1) * bs && i < n; ++i) 
      f[i] = nf[i];

    // for (int i = 0; i < n; ++i) cerr << f[i] << " "; cerr << endl;

    ops[bi].clear();
  };

  int q = l.size();
  for (int i = 0; i < q; ++i) {
    int lf = l[i], rt = r[i];
    int bl = l[i] / bs, br = r[i] / bs;
    refresh(bl); refresh(br); 
    for (int j = l[i]; j <= r[i]; ) {
      if (j % bs == 0 && (j + bs - 1) <= r[i]) {
        ops[j / bs].push_back(v[i]);
        j += bs;
      } else {
        f[j] = max(0, min(f[j] + v[i], c[j]));
        j += 1;
      }
    }
  }

  for (int i = 0; i < n; i += bs)
    refresh(i / bs);
  return f;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:110:9: warning: unused variable 'lf' [-Wunused-variable]
  110 |     int lf = l[i], rt = r[i];
      |         ^~
candies.cpp:110:20: warning: unused variable 'rt' [-Wunused-variable]
  110 |     int lf = l[i], rt = r[i];
      |                    ^~

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