oj.uz

Submission #979361

# Submission time Handle Problem Language Result Execution time Memory
979361 2024-05-10T17:16:32 Z Isam Distributing Candies (IOI21_candies) C++17
100 / 100
 2484 ms 495084 KB 
#include "candies.h"
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
const int BS = 333;
 
 
vector<ll> compute_function(const vector<int>& ops) {
  vector<ll> stk;
  stk.push_back(4e18);
  stk.push_back(2e18);
  for (auto delta : ops) {
    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);
          break;
        }
        rem -= (x - px);
        stk.pop_back();
      }
    }
  }
  
  stk.push_back(0);
  stk.push_back(0);
  reverse(stk.begin(), stk.end());
  return stk;
}
 
vector<int> distribute_candies(
    vector<int> c, vector<int> l,
    vector<int> r, vector<int> v) {
  int n = c.size();
 
  
  // Sort each bucket increasingly by c[i] to facilitate easy evaluation of f.
  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;
  vector<int> a(n, 0), na(n, 0);
  vector<vector<int>> ops(n / BS + 1);
 
  auto commit = [&](int bi) {
    if (ops[bi].empty()) return;
    int l = bi * BS, r = min(n, (bi + 1) * BS);
 
    // compute f(.) and evaluate it in all c[i] of this bucket
    auto stk = compute_function(ops[bi]);
    ll value = 0;
    int ptr = 0;
    for (int i = l; i < r; ++i) {
      int ci = c[order[i]];
      while (stk[ptr + 1] < ci) {
        if (ptr % 2 == 0)
          value += stk[ptr + 1] - stk[ptr];
        ++ptr;
      }
      if (ptr % 2 == 0) {
        na[order[i]] = value + (ci - stk[ptr]);
      } else {
        na[order[i]] = value;
      }
    }
  
    // Adapt for non-zero initial values.
    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 = l; i < r; ++i) {
      ll hi = min(c[i] - maxd, (ll)a[i]);
      ll lo = -mind;
      if (lo < hi) 
        na[i] += hi - lo; 
    }
 
    // Housekeeping.
    for (int i = l; i < r; ++i) 
      a[i] = na[i];
    ops[bi].clear();
  };
 
  int q = l.size();
  for (int i = 0; i < q; ++i) {
    int bl = l[i] / BS, br = r[i] / BS;
    commit(bl); commit(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 {
        a[j] = max(0, min(a[j] + v[i], c[j]));
        j += 1;
      }
    }
  }
 
  for (int i = 0; i < n; i += BS)
    commit(i / BS);
  return a;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 4 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 11716 KB Output is correct
2 Correct 1535 ms 11808 KB Output is correct
3 Correct 1367 ms 11928 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 282 ms 5092 KB Output is correct
3 Correct 54 ms 5204 KB Output is correct
4 Correct 1127 ms 11868 KB Output is correct
5 Correct 1120 ms 18128 KB Output is correct
6 Correct 1134 ms 18516 KB Output is correct
7 Correct 966 ms 17756 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 303 ms 9416 KB Output is correct
4 Correct 59 ms 9044 KB Output is correct
5 Correct 2467 ms 490300 KB Output is correct
6 Correct 2484 ms 494512 KB Output is correct
7 Correct 2443 ms 495084 KB Output is correct
8 Correct 2468 ms 493724 KB Output is correct
9 Correct 1911 ms 495004 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 1345 ms 11716 KB Output is correct
7 Correct 1535 ms 11808 KB Output is correct
8 Correct 1367 ms 11928 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 282 ms 5092 KB Output is correct
11 Correct 54 ms 5204 KB Output is correct
12 Correct 1127 ms 11868 KB Output is correct
13 Correct 1120 ms 18128 KB Output is correct
14 Correct 1134 ms 18516 KB Output is correct
15 Correct 966 ms 17756 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 303 ms 9416 KB Output is correct
19 Correct 59 ms 9044 KB Output is correct
20 Correct 2467 ms 490300 KB Output is correct
21 Correct 2484 ms 494512 KB Output is correct
22 Correct 2443 ms 495084 KB Output is correct
23 Correct 2468 ms 493724 KB Output is correct
24 Correct 1911 ms 495004 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 58 ms 6608 KB Output is correct
27 Correct 298 ms 7652 KB Output is correct
28 Correct 1598 ms 16220 KB Output is correct
29 Correct 1471 ms 16796 KB Output is correct
30 Correct 1363 ms 17184 KB Output is correct
31 Correct 1237 ms 17112 KB Output is correct
32 Correct 1122 ms 17500 KB Output is correct