Submission #988365

#	Time	Username	Problem	Language	Result	Execution time	Memory
988365		cig32	Distributing Candies (IOI21_candies)	C++17	8 / 100	1967 ms	68656 KiB

candies

#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;
    }
    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: 0 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33