oj.uz

Submission #435818

# Submission time Handle Problem Language Result Execution time Memory
435818 2021-06-23T18:41:39 Z bicsi Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 10028 KB 
#include "candies.h"
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
const int BS = 1024;
 

vector<int> compute_function(const vector<int>& ops) {
  vector<int> stk;
  stk.push_back(2e9);
  stk.push_back(2e9);
  for (auto delta : ops) {
    if (delta == 0) continue;
    if (delta > 0) {
      int rem = delta, px = 0;
      while (true) {
        int 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 {
      int rem = -delta;
      while (true) {
        int px = stk.back(); stk.pop_back();
        int 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<int> 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]);
    int value = 0;
    int ptr = 0;
    for (int i = bi * BS; i < (bi + 1) * BS && i < n; ++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 = bi * BS; i < (bi + 1) * BS && i < n; ++i) {
      ll hi = min(c[i] - maxd, (ll)a[i]);
      ll lo = -mind;
      if (lo < hi) 
        na[i] += hi - lo; 
    }
 
    // Housekeeping.
    for (int i = bi * BS; i < (bi + 1) * BS && i < n; ++i) 
      a[i] = na[i];
    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;
    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;
}

Compilation message

candies.cpp: In lambda function:
candies.cpp:72:9: warning: unused variable 'l' [-Wunused-variable]
   72 |     int l = bi * BS, r = min(n, (bi + 1) * BS);
      |         ^
candies.cpp:72:22: warning: unused variable 'r' [-Wunused-variable]
   72 |     int l = bi * BS, r = min(n, (bi + 1) * BS);
      |                      ^
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:114:9: warning: unused variable 'lf' [-Wunused-variable]
  114 |     int lf = l[i], rt = r[i];
      |         ^~
candies.cpp:114:20: warning: unused variable 'rt' [-Wunused-variable]
  114 |     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 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 7 ms 372 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 621 ms 4960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.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 Runtime error 156 ms 10028 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

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 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 7 ms 372 KB Output is correct
6 Execution timed out 5048 ms 9480 KB Time limit exceeded
7 Halted 0 ms 0 KB -