oj.uz

Submission #988382

# Submission time Handle Problem Language Result Execution time Memory
988382 2024-05-24T15:00:09 Z cig32 Distributing Candies (IOI21_candies) C++17
100 / 100
 2306 ms 75492 KB 
#include "candies.h"

#include <vector>
#include "bits/stdc++.h"
using namespace std;
#define int long long
struct segtree_basic {
  struct node {
    int lazy;
    int lc, rc;
    int mx, mn;
    int sum;
    int type; // 1: ADD, 2: SET
  };
  vector<node> st;
  int stok;
  void init(int l, int r, int idx) {
    st[idx].lazy = 0;
    st[idx].sum = 0;
    st[idx].mx = st[idx].mn = 0;
    st[idx].type = 1;
    st[idx].lc = l, st[idx].rc = r;
    if(l == r) return;
    init(l, (l + r) >> 1, (idx << 1) + 1);
    init(((l + r) >> 1) + 1, r, (idx << 1) + 2);
  }
  void push_down(int idx) {
    if(st[idx].type == 1 && st[idx].lazy == 0) {
      // no update
      return;
    }
    if(st[idx].type == 1) {
      st[(idx << 1) + 1].lazy += st[idx].lazy;
      st[(idx << 1) + 1].mx += st[idx].lazy;
      st[(idx << 1) + 1].mn += st[idx].lazy;
      st[(idx << 1) + 1].sum += st[idx].lazy * (st[(idx << 1) + 1].rc - st[(idx << 1) + 1].lc + 1);
      st[(idx << 1) + 2].lazy += st[idx].lazy;
      st[(idx << 1) + 2].mx += st[idx].lazy;
      st[(idx << 1) + 2].mn += st[idx].lazy;
      st[(idx << 1) + 2].sum += st[idx].lazy * (st[(idx << 1) + 2].rc - st[(idx << 1) + 2].lc + 1);
    }
    else {
      st[(idx << 1) + 1].lazy = st[idx].lazy;
      st[(idx << 1) + 1].mx = st[idx].lazy;
      st[(idx << 1) + 1].mn = st[idx].lazy;
      st[(idx << 1) + 1].sum = st[idx].lazy * (st[(idx << 1) + 1].rc - st[(idx << 1) + 1].lc + 1);
      st[(idx << 1) + 1].type = 2;
      st[(idx << 1) + 2].lazy = st[idx].lazy;
      st[(idx << 1) + 2].mx = st[idx].lazy;
      st[(idx << 1) + 2].mn = st[idx].lazy;
      st[(idx << 1) + 2].sum = st[idx].lazy * (st[(idx << 1) + 2].rc - st[(idx << 1) + 2].lc + 1);
      st[(idx << 1) + 2].type = 2;
    }
    st[idx].type = 1;
    st[idx].lazy = 0;
  }
  void push_up(int idx) {
    st[idx].mn = min(st[(idx << 1) + 1].mn, st[(idx << 1) + 2].mn);
    st[idx].mx = max(st[(idx << 1) + 1].mx, st[(idx << 1) + 2].mx);
    st[idx].sum = st[(idx << 1) + 1].sum + st[(idx << 1) + 2].sum;
  }
  void u1(int l, int r, int constl, int constr, int idx, int val) {
    if(l <= constl && constr <= r) {
      st[idx].lazy += val;
      st[idx].mn += val, st[idx].mx += val;
      st[idx].sum += val * (st[idx].rc - st[idx].lc + 1);
      return;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) u1(l, r, mid+1, constr, (idx << 1) + 2, val);
    else if(constr < l || r < mid+1) u1(l, r, constl, mid, (idx << 1) + 1, val);
    else {
      u1(l, r, constl, mid, (idx << 1) + 1, val);
      u1(l, r, mid + 1, constr, (idx << 1) + 2, val);
    }
    push_up(idx);
  }
  void u2(int l, int r, int constl, int constr, int idx, int val) {
    if(l <= constl && constr <= r) {
      st[idx].type = 2;
      st[idx].lazy = val;
      st[idx].mn = val, st[idx].mx = val;
      st[idx].sum = val * (st[idx].rc - st[idx].lc + 1);
      return;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) u2(l, r, mid+1, constr, (idx << 1) + 2, val);
    else if(constr < l || r < mid+1) u2(l, r, constl, mid, (idx << 1) + 1, val);
    else {
      u2(l, r, constl, mid, (idx << 1) + 1, val);
      u2(l, r, mid + 1, constr, (idx << 1) + 2, val);
    }
    push_up(idx);
  }
  int qu1(int l, int r, int constl, int constr, int idx) {
    if(l <= constl && constr <= r) return st[idx].mn;
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu1(l, r, mid+1, constr, (idx << 1) + 2);
    else if(constr < l || r< mid+1) return qu1(l, r, constl, mid, (idx << 1) + 1);
    else {
      return min(
        qu1(l, r, constl, mid, (idx << 1) + 1),
        qu1(l, r, mid+1, constr, (idx << 1) + 2)
      );
    }
  }
  int qu2(int l, int r, int constl, int constr, int idx) {
    if(l <= constl && constr <= r) return st[idx].mx;
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu2(l, r, mid+1, constr, (idx << 1) + 2);
    else if(constr < l || r< mid+1) return qu2(l, r, constl, mid, (idx << 1) + 1);
    else {
      return max(
        qu2(l, r, constl, mid, (idx << 1) + 1),
        qu2(l, r, mid+1, constr, (idx << 1) + 2)
      );
    }
  }
  int qu3(int l, int r, int constl, int constr, int idx) {
    if(l <= constl && constr <= r) return st[idx].sum;
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu3(l, r, mid+1, constr, (idx << 1) + 2);
    else if(constr < l || r< mid+1) return qu3(l, r, constl, mid, (idx << 1) + 1);
    else {
      return qu3(l, r, constl, mid, (idx << 1) + 1) + qu3(l, r, mid+1, constr, (idx << 1) + 2);
    }
  }
  int qu4(int l, int r, int constl, int constr, int idx, int val) {
    if(l <= constl && constr <= r) {
      if(st[idx].mx < val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[(idx << 1) + 1].mx >= val) idx = (idx << 1) + 1, constr = mid;
        else idx = (idx << 1) + 2, constl = mid + 1;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu4(l, r, mid+1, constr, (idx << 1) + 2, val);
    else if(constr < l || r< mid+1) return qu4(l, r, constl, mid, (idx << 1) + 1, val);
    else {
      int lc = qu4(l, r, constl, mid, (idx << 1) + 1, val);
      if(lc != -1) return lc;
      return qu4(l, r, mid+1, constr, (idx << 1) + 2, val);
    }
  }
  int qu5(int l, int r, int constl, int constr, int idx, int val) {
    if(l <= constl && constr <= r) {
      if(st[idx].mn > val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[(idx << 1) + 1].mn <= val) idx = (idx << 1) + 1, constr = mid;
        else idx = (idx << 1) + 2, constl = mid + 1;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu5(l, r, mid+1, constr, (idx << 1) + 2, val);
    else if(constr < l || r< mid+1) return qu5(l, r, constl, mid, (idx << 1) + 1, val);
    else {
      int lc = qu5(l, r, constl, mid, (idx << 1) + 1, val);
      if(lc != -1) return lc;
      return qu5(l, r, mid+1, constr, (idx << 1) + 2, val);
    }
  }
  int qu6(int l, int r, int constl, int constr, int idx, int val) {
    if(l <= constl && constr <= r) {
      if(st[idx].mx < val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[(idx << 1) + 2].mx >= val) idx = (idx << 1) + 2, constl = mid + 1;
        else idx = (idx << 1) + 1, constr = mid;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu6(l, r, mid+1, constr, (idx << 1) + 2, val);
    else if(constr < l || r< mid+1) return qu6(l, r, constl, mid, (idx << 1) + 1, val);
    else {
      int rc = qu6(l, r, mid+1, constr, (idx << 1) + 2, val);
      if(rc != -1) return rc;
      return qu6(l, r, constl, mid, (idx << 1) + 1, val);
    }
  }
  int qu7(int l, int r, int constl, int constr, int idx, int val) {
    if(l <= constl && constr <= r) {
      if(st[idx].mn > val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[(idx << 1) + 2].mn <= val) idx = (idx << 1) + 2, constl = mid + 1;
        else idx = (idx << 1) + 1, constr = mid;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu7(l, r, mid+1, constr, (idx << 1) + 2, val);
    else if(constr < l || r< mid+1) return qu7(l, r, constl, mid, (idx << 1) + 1, val);
    else {
      int rc = qu7(l, r, mid+1, constr, (idx << 1) + 2, val);
      if(rc != -1) return rc;
      return qu7(l, r, constl, mid, (idx << 1) + 1, val);
    }
  }
  
  void resize(int k) {
    stok = k + 5;
    st.resize(4 * stok);
    init(0, stok, 0);
  }
 
  void range_add(int l, int r, int v) { u1(l, r, 0, stok, 0, v); }
  void range_assign(int l, int r, int v) { u2(l, r, 0, stok, 0, v); }
  int query_min(int l, int r) { return qu1(l, r, 0, stok, 0); }
  int query_max(int l, int r) { return qu2(l ,r, 0, stok, 0); }
  int query_sum(int l, int r) { return qu3(l, r, 0, stok, 0); }
  int query_firstAtLeast(int l, int r, int v) { return qu4(l, r, 0, stok, 0, v); }
  int query_firstAtMost(int l, int r, int v) { return qu5(l, r, 0, stok, 0, v); }
  int query_lastAtLeast(int l, int r, int v) { return qu6(l, r, 0, stok, 0, v); }
  int query_lastAtMost(int l, int r, int v) { return qu7(l, r, 0, stok, 0, v); }
  
 
};
#undef int

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();
  std::vector<int> s(n, 0);
  #define int long long
  vector<int> ins[n+1], del[n+1];
  int m = l.size();
  segtree_basic stb;
  stb.resize(m);
  for(int i=0; i<m; i++) {
    ins[l[i]].push_back(i);
    del[r[i] + 1].push_back(i);
  }
  for(int i=0; i<n; i++) {
    for(int x: del[i]) {
      stb.range_add(x + 1, m, -v[x]);
    }
    for(int x: ins[i]) {
      stb.range_add(x + 1, m, v[x]);
    }
    int res = stb.query_sum(m, m);
    int lb = 0, rb = m;
    while(lb < rb) {
      int mid = (lb + rb + 1) >> 1;
      int mx = stb.query_max(mid, m);
      int mn = stb.query_min(mid, m);
      if(mx - mn > c[i]) lb = mid;
      else rb = mid - 1;
    }
    int mx = stb.query_max(lb, m);
    int mn = stb.query_min(lb, m);
    int dist = mx - mn;
    if(dist <= c[i]) {
      s[i] = res - mn;
    }
    else {
      int buh = stb.query_max(lb, lb);
      if(buh > res) {
        buh -= dist;
        s[i] = res - buh;
      }
      else {
        buh += dist;
        s[i] = c[i] - (buh - res);
      }
    }
  }

  return s;
}

/*
g++ -std=c++17 -O2 -o candies buh.cpp candies.cpp
./candies < input.txt

*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 4 ms 864 KB Output is correct
5 Correct 10 ms 1116 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1933 ms 73500 KB Output is correct
2 Correct 2027 ms 72728 KB Output is correct
3 Correct 2055 ms 72556 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 384 ms 57428 KB Output is correct
3 Correct 631 ms 15500 KB Output is correct
4 Correct 2306 ms 74564 KB Output is correct
5 Correct 2155 ms 74964 KB Output is correct
6 Correct 1568 ms 75492 KB Output is correct
7 Correct 1602 ms 74688 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 166 ms 54988 KB Output is correct
4 Correct 478 ms 13904 KB Output is correct
5 Correct 1486 ms 67580 KB Output is correct
6 Correct 1337 ms 68256 KB Output is correct
7 Correct 1322 ms 68832 KB Output is correct
8 Correct 1451 ms 67480 KB Output is correct
9 Correct 1661 ms 68964 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 4 ms 864 KB Output is correct
5 Correct 10 ms 1116 KB Output is correct
6 Correct 1933 ms 73500 KB Output is correct
7 Correct 2027 ms 72728 KB Output is correct
8 Correct 2055 ms 72556 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 384 ms 57428 KB Output is correct
11 Correct 631 ms 15500 KB Output is correct
12 Correct 2306 ms 74564 KB Output is correct
13 Correct 2155 ms 74964 KB Output is correct
14 Correct 1568 ms 75492 KB Output is correct
15 Correct 1602 ms 74688 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 166 ms 54988 KB Output is correct
19 Correct 478 ms 13904 KB Output is correct
20 Correct 1486 ms 67580 KB Output is correct
21 Correct 1337 ms 68256 KB Output is correct
22 Correct 1322 ms 68832 KB Output is correct
23 Correct 1451 ms 67480 KB Output is correct
24 Correct 1661 ms 68964 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 577 ms 13988 KB Output is correct
27 Correct 340 ms 57256 KB Output is correct
28 Correct 1907 ms 73296 KB Output is correct
29 Correct 1772 ms 73592 KB Output is correct
30 Correct 1756 ms 73788 KB Output is correct
31 Correct 1617 ms 73984 KB Output is correct
32 Correct 1574 ms 74184 KB Output is correct