oj.uz

Submission #768437

# Submission time Handle Problem Language Result Execution time Memory
768437 2023-06-28T07:18:33 Z Soumya1 Distributing Candies (IOI21_candies) C++17
100 / 100
 372 ms 38124 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 5;
long long mn[4 * mxN], mx[4 * mxN], lazy[4 * mxN];
void operate(int x, long long v) {
  mn[x] += v;
  mx[x] += v;
  lazy[x] += v;
}
void push(int x, int lx, int rx) {
  if (lx == rx) return;
  operate(x << 1, lazy[x]);
  operate(x << 1 | 1, lazy[x]);
  lazy[x] = 0;
}
void update(int x, int lx, int rx, int l, int r, int v) {
  if (lazy[x]) push(x, lx, rx);
  if (l > rx || lx > r) return;
  if (l <= lx && r >= rx) {
    operate(x, v);
    return;
  }
  int m = (lx + rx) >> 1;
  update(x << 1, lx, m, l, r, v);
  update(x << 1 | 1, m + 1, rx, l, r, v);
  mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
  mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}
long long sum;
int query(int x, int lx, int rx, long long cmn, long long cmx, int c) {
  if (lazy[x]) push(x, lx, rx);
  if (lx == rx) {
    cmx = max(cmx, mx[x]);
    cmn = min(cmn, mn[x]);
    if (cmx - cmn < c) return sum - cmn;
    if (mx[x] < cmx) return sum - (cmx - c);
    return sum - cmn;
  }
  int m = (lx + rx) >> 1;
  if (max(cmx, mx[x << 1 | 1]) - min(cmn, mn[x << 1 | 1]) >= c) return query(x << 1 | 1, m + 1, rx, cmn, cmx, c);
  return query(x << 1, lx, m, min(cmn, mn[x << 1 | 1]), max(cmx, mx[x << 1 | 1]), c);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
  int n = c.size();
  vector<pair<int, int>> updates[n];
  for (int i = 0; i < l.size(); i++) {
    updates[l[i]].push_back({i + 2, v[i]});
    if (r[i] < n - 1) updates[r[i] + 1].push_back({i + 2, -v[i]});
  }
  int Q = l.size() + 2;
  vector<int> ans(n);
  for (int i = 0; i < n; i++) {
    for (auto [j, val] : updates[i]) {
      sum += val;
      update(1, 1, Q, j, Q, val);
    }
    ans[i] = query(1, 1, Q, sum, sum, c[i]);
  }
  return ans;
}

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:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int i = 0; i < l.size(); i++) {
      |                   ~~^~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 576 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 32092 KB Output is correct
2 Correct 304 ms 35384 KB Output is correct
3 Correct 298 ms 35320 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 174 ms 24808 KB Output is correct
3 Correct 47 ms 10920 KB Output is correct
4 Correct 287 ms 37324 KB Output is correct
5 Correct 297 ms 37700 KB Output is correct
6 Correct 307 ms 38124 KB Output is correct
7 Correct 288 ms 37360 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 83 ms 21708 KB Output is correct
4 Correct 45 ms 8816 KB Output is correct
5 Correct 133 ms 28988 KB Output is correct
6 Correct 133 ms 29008 KB Output is correct
7 Correct 134 ms 29040 KB Output is correct
8 Correct 131 ms 28964 KB Output is correct
9 Correct 127 ms 28964 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 576 KB Output is correct
6 Correct 303 ms 32092 KB Output is correct
7 Correct 304 ms 35384 KB Output is correct
8 Correct 298 ms 35320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 174 ms 24808 KB Output is correct
11 Correct 47 ms 10920 KB Output is correct
12 Correct 287 ms 37324 KB Output is correct
13 Correct 297 ms 37700 KB Output is correct
14 Correct 307 ms 38124 KB Output is correct
15 Correct 288 ms 37360 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 83 ms 21708 KB Output is correct
19 Correct 45 ms 8816 KB Output is correct
20 Correct 133 ms 28988 KB Output is correct
21 Correct 133 ms 29008 KB Output is correct
22 Correct 134 ms 29040 KB Output is correct
23 Correct 131 ms 28964 KB Output is correct
24 Correct 127 ms 28964 KB Output is correct
25 Correct 0 ms 308 KB Output is correct
26 Correct 46 ms 8772 KB Output is correct
27 Correct 174 ms 24484 KB Output is correct
28 Correct 299 ms 35984 KB Output is correct
29 Correct 328 ms 36464 KB Output is correct
30 Correct 318 ms 36456 KB Output is correct
31 Correct 372 ms 36792 KB Output is correct
32 Correct 290 ms 36924 KB Output is correct