oj.uz

Submission #883594

# Submission time Handle Problem Language Result Execution time Memory
883594 2023-12-05T13:33:00 Z nguyentunglam Distributing Candies (IOI21_candies) C++17
100 / 100
 4219 ms 59312 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long
using namespace std;

const int N = 2e5 + 10;

int L[N], R[N], last[N], mx[N], mn[N];

array<long long, 3> T[N << 2];

array<long long, 3> zero = {0, 0, 0};

vector<int> query[N];

void add (array<long long, 3> &a, array<long long, 3> b) {
  a[1] = min(a[1], a[0] + b[1]);
  a[2] = max(a[2], a[0] + b[2]);
  a[0] += b[0];
}

void push(int s, int l, int r) {
  if (l == r || T[s] == zero) return;
  add(T[s << 1], T[s]);
  add(T[s << 1 | 1], T[s]);
  T[s] = zero;
}

void up(int s, int l, int r, int from, int to, int val) {
  push(s, l, r);
  if (l > to || r < from) return;
  if (from <= l && r <= to) {
    add(T[s], {val, val, val});
    return;
  }
  int mid = l + r >> 1;
  up(s << 1, l, mid, from, to, val);
  up(s << 1 | 1, mid + 1, r, from, to, val);
}

array<long long, 3> get(int s, int l, int r, int pos) {
  push(s, l, r);
  if (l == r)  return T[s];
  int mid = l + r >> 1;
  if (pos <= mid) return get(s << 1, l, mid, pos);
  return get(s << 1 | 1, mid + 1, r, pos);
}

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

  l.insert(l.begin(), 0);
  l.insert(l.begin(), 0);

  r.insert(r.begin(), n - 1);
  r.insert(r.begin(), n - 1);

  v.insert(v.begin(), -2e9);
  v.insert(v.begin(), 2e9);

  int q = v.size();

  for(int i = 0; i < n; i++) {
    L[i] = 0; R[i] = q - 1;
  }

  for(int loop = 1; loop <= 20; loop++) {
    bool valid = 0;
    for(int i = 0; i < n; i++) if (L[i] <= R[i]) {
      query[L[i] + R[i] >> 1].push_back(i);
      valid = 1;
    }
    if (!valid) break;


    for(int i = q - 1; i >= 0; i--) {
      for(int &j : query[i]) {
        array<ll, 3> tmp = get(1, 0, n - 1, j);
        if (tmp[2] - tmp[1] <= c[j]) {
          R[j] = i - 1;
          last[j] = i;
          mn[j] = tmp[1];
          mx[j] = tmp[2];
        } else L[j] = i + 1;
      } query[i].clear();
      up(1, 0, n - 1, l[i], r[i], -v[i]);
    }

    for(int i = 1; i <= 4 * n; i++) T[i] = zero;
  }

  for(int i = 0; i < n; i++) {
    int j = last[i];
    if (v[j] > 0) p[i] = c[i] - mx[i];
    else p[i] = -mn[i];
  }

  return p;
}


#ifdef ngu
  int32_t main() {

    freopen ("task.inp", "r", stdin);
    freopen ("task.out", "w", stdout);

    int n; cin >> n;

    vector<int> c(n);

    for(int i = 0; i < n; i++) cin >> c[i];

    int q; cin >> q;

    vector<int> l(q), r(q), v(q);

    for(int i = 0; i < q; i++) cin >> l[i] >> r[i] >> v[i];

    vector<int> ans = distribute_candies(c, l, r, v);

    for(int &j : ans) cout << j << " ";
  }
#endif // ngu

Compilation message

candies.cpp: In function 'void up(int, int, int, int, int, int)':
candies.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int mid = l + r >> 1;
      |             ~~^~~
candies.cpp: In function 'std::array<long long int, 3> get(int, int, int, int)':
candies.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid = l + r >> 1;
      |             ~~^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:75:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |       query[L[i] + R[i] >> 1].push_back(i);
      |             ~~~~~^~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 5 ms 10960 KB Output is correct
4 Correct 8 ms 10844 KB Output is correct
5 Correct 15 ms 11140 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4170 ms 51200 KB Output is correct
2 Correct 4204 ms 57148 KB Output is correct
3 Correct 4219 ms 57364 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 1653 ms 18892 KB Output is correct
3 Correct 394 ms 43020 KB Output is correct
4 Correct 3986 ms 55652 KB Output is correct
5 Correct 4030 ms 59312 KB Output is correct
6 Correct 3892 ms 56296 KB Output is correct
7 Correct 3919 ms 55636 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 102 ms 18356 KB Output is correct
4 Correct 396 ms 41024 KB Output is correct
5 Correct 760 ms 54048 KB Output is correct
6 Correct 764 ms 54648 KB Output is correct
7 Correct 668 ms 54760 KB Output is correct
8 Correct 787 ms 54444 KB Output is correct
9 Correct 655 ms 55020 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 5 ms 10960 KB Output is correct
4 Correct 8 ms 10844 KB Output is correct
5 Correct 15 ms 11140 KB Output is correct
6 Correct 4170 ms 51200 KB Output is correct
7 Correct 4204 ms 57148 KB Output is correct
8 Correct 4219 ms 57364 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 1653 ms 18892 KB Output is correct
11 Correct 394 ms 43020 KB Output is correct
12 Correct 3986 ms 55652 KB Output is correct
13 Correct 4030 ms 59312 KB Output is correct
14 Correct 3892 ms 56296 KB Output is correct
15 Correct 3919 ms 55636 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 102 ms 18356 KB Output is correct
19 Correct 396 ms 41024 KB Output is correct
20 Correct 760 ms 54048 KB Output is correct
21 Correct 764 ms 54648 KB Output is correct
22 Correct 668 ms 54760 KB Output is correct
23 Correct 787 ms 54444 KB Output is correct
24 Correct 655 ms 55020 KB Output is correct
25 Correct 2 ms 10840 KB Output is correct
26 Correct 424 ms 40780 KB Output is correct
27 Correct 1688 ms 18592 KB Output is correct
28 Correct 3988 ms 54968 KB Output is correct
29 Correct 4035 ms 56680 KB Output is correct
30 Correct 4075 ms 55992 KB Output is correct
31 Correct 3871 ms 55296 KB Output is correct
32 Correct 4061 ms 55388 KB Output is correct