oj.uz

Submission #810442

# Submission time Handle Problem Language Result Execution time Memory
810442 2023-08-06T09:49:52 Z WLZ Distributing Candies (IOI21_candies) C++17
27 / 100
 746 ms 113304 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll LINF = (ll) 1e18;
const int SZ = (1 << 22);

ll mx[SZ], mn[SZ], lazy_add[SZ];

void push_add(int idx) {
  if (lazy_add[idx] == 0) return;
  mx[idx] += lazy_add[idx]; mn[idx] += lazy_add[idx];
  if (2 * idx + 1 < SZ) {
    lazy_add[2 * idx] += lazy_add[idx];
    lazy_add[2 * idx + 1] += lazy_add[idx];
  }
  lazy_add[idx] = 0;
}

void add(int idx, int cl, int cr, int l, int r, int val) {
  push_add(idx);
  if (cl > r || cr < l) return;
  if (l <= cl && cr <= r) {
    lazy_add[idx] += val;
    push_add(idx);
    return;
  }
  int mid = (cl + cr) / 2;
  add(2 * idx, cl, mid, l, r, val); add(2 * idx + 1, mid + 1, cr, l, r, val);
  mx[idx] = max(mx[2 * idx], mx[2 * idx + 1]);
  mn[idx] = min(mn[2 * idx], mn[2 * idx + 1]);
}

void max_eq(int idx, int cl, int cr, int l, int r, ll val) {
  push_add(idx);
  if (cl > r || cr < l || mn[idx] >= val) return;
  if (l <= cl && cr <= r && mx[idx] < val) add(idx, cl, cr, l, r, val - mx[idx]);
  int mid = (cl + cr) / 2;
  max_eq(2 * idx, cl, mid, l, r, val); max_eq(2 * idx + 1, mid + 1, cr, l, r, val);
  mx[idx] = max(mx[2 * idx], mx[2 * idx + 1]);
  mn[idx] = min(mn[2 * idx], mn[2 * idx + 1]);
}

void min_eq(int idx, int cl, int cr, int l, int r, ll val) {
  push_add(idx);
  if (cl > r || cr < l || mx[idx] <= val) return;
  if (l <= cl && cr <= r && mn[idx] > val) add(idx, cl, cr, l, r, val - mn[idx]);
  int mid = (cl + cr) / 2;
  min_eq(2 * idx, cl, mid, l, r, val); min_eq(2 * idx + 1, mid + 1, cr, l, r, val);
  mx[idx] = max(mx[2 * idx], mx[2 * idx + 1]);
  mn[idx] = min(mn[2 * idx], mn[2 * idx + 1]);
}

vector<int> ans;

void calc_ans(int idx, int cl, int cr) {
  push_add(idx);
  if (cl == cr) {
    ans[cl] = mx[idx];
    return;
  }
  int mid = (cl + cr) / 2;
  calc_ans(2 * idx, cl, mid);
  calc_ans(2 * idx + 1, mid + 1, cr);
}

int n, q;

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
  n = (int) c.size(), q = (int) l.size();
  memset(mx, 0, sizeof mx);
  memset(mn, 0, sizeof mn);
  memset(lazy_add, 0, sizeof lazy_add);
  for (int i = 0; i < q; i++) {
    add(1, 0, n - 1, l[i], r[i], v[i]);
    max_eq(1, 0, n - 1, 0, n - 1, 0);
    min_eq(1, 0, n - 1, 0, n - 1, c[0]);
  }
  ans.resize(n);
  calc_ans(1, 0, n - 1);
  return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98684 KB Output is correct
2 Incorrect 40 ms 98684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 457 ms 106600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 98772 KB Output is correct
2 Correct 149 ms 103516 KB Output is correct
3 Correct 75 ms 103036 KB Output is correct
4 Correct 315 ms 112432 KB Output is correct
5 Correct 439 ms 112920 KB Output is correct
6 Correct 746 ms 113304 KB Output is correct
7 Correct 560 ms 112604 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 98772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98684 KB Output is correct
2 Incorrect 40 ms 98684 KB Output isn't correct
3 Halted 0 ms 0 KB -