Submission #549049

#	Time	Username	Problem	Language	Result	Execution time	Memory
549049		cig32	사탕 분배 (IOI21_candies)	C++17	100 / 100	2753 ms	49432 KiB

candies

#include "candies.h"
#include "bits/stdc++.h"
using namespace std;

#include <cassert>
#include <cstdio>
#include <vector>

struct segtree {
  struct node {
    int64_t upd = 0, mi = 0, ma = 0;
  };
  vector<node> st;
  int64_t stok;
  void push_down(int64_t idx) {
    st[2*idx+1].upd += st[idx].upd;
    st[2*idx+1].mi += st[idx].upd;
    st[2*idx+1].ma += st[idx].upd;
    st[2*idx+2].upd += st[idx].upd;
    st[2*idx+2].mi += st[idx].upd;
    st[2*idx+2].ma += st[idx].upd;
    st[idx].upd = 0;
  }
  void u(int64_t l, int64_t r, int64_t constl, int64_t constr, int64_t idx, int64_t val) {
    if(l <= constl && constr <= r) {
      st[idx].upd += val;
      st[idx].mi += val;
      st[idx].ma += val;
      return;
    }
    int64_t mid = (constl  +constr) >> 1;
    //almst forgot
    push_down(idx);
    if(mid <l || r <constl) u(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr<l || r<mid+1) u(l, r, constl, mid, 2*idx+1, val);
    else{
      u(l, r, constl, mid, 2*idx+1, val);
      u(l, r, mid+1, constr, 2*idx+2, val);
    }
    st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi);
    st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma);
  }
  int64_t qu1(int64_t l, int64_t r, int64_t constl, int64_t constr, int64_t idx) {
    if(l <= constl && constr <= r) return st[idx].mi;
    int64_t mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid< l || r<constl) return qu1(l, r, mid+1, constr, 2*idx+2);
    else if(constr<l || r<mid+1) return qu1(l, r, constl, mid, 2*idx+1);
    return min(qu1(l, r, constl, mid, 2*idx+1), qu1(l, r, mid+1, constr, 2*idx+2));
  }
  int64_t qu2(int64_t l, int64_t r, int64_t constl, int64_t constr, int64_t idx) {
    if(l <= constl && constr <= r) return st[idx].ma;
    int64_t mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid< l || r<constl) return qu2(l, r, mid+1, constr, 2*idx+2);
    else if(constr<l || r<mid+1) return qu2(l, r, constl, mid, 2*idx+1);
    return max(qu2(l, r, constl, mid, 2*idx+1), qu2(l, r, mid+1, constr, 2*idx+2));
  }
  public:
  void resize(int64_t k) {
    stok = k;
    st.resize(4*k + 10);
  }
  void range_add(int64_t l, int64_t r, int64_t v) {
    u(l, r, 0, stok, 0, v);
  }
  int64_t query_min(int64_t l, int64_t r) {
    return qu1(l, r, 0, stok, 0);
  }
  int64_t query_max(int64_t l, int64_t r) {
    return qu2(l, r, 0, stok, 0);
  }
};

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);
  int q = l.size();
  segtree owo;
  owo.resize(q + 2);
  owo.range_add(0, 0, 1e15);
  owo.range_add(1, 1, 0);
  vector<int> in[n+1], out[n+1];
  for(int i=0; i<q; i++) {
    in[l[i]].push_back(i);
    out[r[i]+1].push_back(i);
  }
  for(int i=0; i<n; i++) {
    for(int xxxX : in[i]) {
      int x = xxxX + 2;
      int val = v[xxxX];
      owo.range_add(x, q + 1, val);
    }
    for(int xxxX: out[i]) {
      int x = xxxX + 2;
      int val = v[xxxX];
      owo.range_add(x, q + 1, -val);
    }
    int lb = 0, rb = q + 1;
    while(lb < rb) {
      int mid = (lb + rb + 1) >> 1;
      if(owo.query_max(mid, q + 1) - owo.query_min(mid, q + 1) >= c[i]) lb = mid;
      else rb = mid - 1;
    } 
    if(owo.query_max(lb, q + 1) - owo.query_min(lb, q + 1) >= c[i]) {
      if(owo.query_max(lb, q + 1) == owo.query_max(lb, lb)) {
        s[i] = owo.query_max(q + 1, q + 1) - owo.query_min(lb, q + 1);
      }
      else {
        s[i] = owo.query_max(q + 1, q + 1) - (owo.query_max(lb, q + 1) - c[i]);
      }
    }
    else {
      s[i] = owo.query_max(q + 1, q + 1);
    }
  }
  return s;
}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33