oj.uz

Submission #435800

# Submission time Handle Problem Language Result Execution time Memory
435800 2021-06-23T18:06:51 Z bicsi Distributing Candies (IOI21_candies) C++17
59 / 100
 5000 ms 627648 KB 
#include "candies.h"
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
const int bs = 512;
 
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);
            break;
          }
          rem -= (x - px);
          stk.pop_back();
        }
      }
    }
    
    stk.push_back(0);
    stk.push_back(0);
    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

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 13 ms 332 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5052 ms 11452 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1002 ms 5028 KB Output is correct
3 Correct 130 ms 5160 KB Output is correct
4 Correct 4703 ms 11576 KB Output is correct
5 Correct 4733 ms 11412 KB Output is correct
6 Correct 3996 ms 11456 KB Output is correct
7 Correct 4003 ms 11460 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2533 ms 8232 KB Output is correct
4 Correct 130 ms 10552 KB Output is correct
5 Correct 4520 ms 627512 KB Output is correct
6 Correct 4528 ms 627648 KB Output is correct
7 Correct 4137 ms 627432 KB Output is correct
8 Correct 4510 ms 627572 KB Output is correct
9 Correct 3861 ms 627392 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 13 ms 332 KB Output is correct
6 Execution timed out 5052 ms 11452 KB Time limit exceeded
7 Halted 0 ms 0 KB -