oj.uz

Submission #810567

# Submission time Handle Problem Language Result Execution time Memory
810567 2023-08-06T11:20:00 Z WLZ Distributing Candies (IOI21_candies) C++17
27 / 100
 697 ms 39820 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 + 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(), SZ = 6 * n + 10;
  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 1 ms 300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 431 ms 38532 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 1 ms 340 KB Output is correct
2 Correct 115 ms 7516 KB Output is correct
3 Correct 57 ms 33728 KB Output is correct
4 Correct 278 ms 39692 KB Output is correct
5 Correct 420 ms 39820 KB Output is correct
6 Correct 697 ms 39768 KB Output is correct
7 Correct 531 ms 39756 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 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 1 ms 300 KB Output isn't correct
3 Halted 0 ms 0 KB -