oj.uz

Submission #810436

# Submission time Handle Problem Language Result Execution time Memory
810436 2023-08-06T09:45:57 Z WLZ Distributing Candies (IOI21_candies) C++17
0 / 100
 93 ms 56088 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

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

vector<ll> mx, mn, lazy_add;

void push_add(int idx) {
  if (lazy_add[idx] == 0) return;
  mx[idx] += lazy_add[idx]; mn[idx] += lazy_add[idx];
  if (2 * idx < 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(), SZ = 4 * n + 5;
  mx.assign(SZ, 0);
  mn.assign(SZ, 0);
  lazy_add.assign(SZ, 0);
  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 1 ms 212 KB Output is correct
2 Incorrect 0 ms 296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 93 ms 56088 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Runtime error 51 ms 13260 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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