Submission #1026887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026887		NeroZein	Distributing Candies (IOI21_candies)	C++17	100 / 100	235 ms	39956 KiB

candies

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

const int N = 2e5 + 5; 

struct node {
  long long sum = 0, min_pref = 0, max_pref = 0; 
}; 

node combine(node lx, node rx) {
  node ret;
  ret.sum = lx.sum + rx.sum;
  ret.min_pref = min(lx.min_pref, lx.sum + rx.min_pref);
  ret.max_pref = max(lx.max_pref, lx.sum + rx.max_pref);
  return ret;
}

node seg[N * 2]; 

void upd(int nd, int l, int r, int p, int v) {
  if (l == r) {
    seg[nd].sum = v;
    seg[nd].min_pref = min(0, v);
    seg[nd].max_pref = max(0, v);
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    upd(nd + 1, l, mid, p, v);
  } else {
    upd(rs, mid + 1, r, p, v); 
  }
  seg[nd] = combine(seg[nd + 1], seg[rs]);
}

int qry(int nd, int l, int r, int c) {
  if (l == r) {
    return max(0LL, min((long long) c, seg[nd].sum)); 
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1); 
  if (seg[rs].max_pref - seg[rs].min_pref >= c) {
    return qry(rs, mid + 1, r, c); 
  }
  int ret = qry(nd + 1, l, mid, c); 
  if (ret + seg[rs].min_pref <= 0) {
    ret = seg[rs].sum - seg[rs].min_pref;
  } else if (ret + seg[rs].max_pref >= c) {
    ret = c + (seg[rs].sum - seg[rs].max_pref);
  } else {
    ret += seg[rs].sum;
  }
  return ret; 
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
  int n = (int) c.size();
  int q = (int) l.size();
  vector<vector<int>> open(n);
  vector<vector<int>> close(n);
  for (int i = 0; i < q; ++i) {
    open[l[i]].push_back(i);
    close[r[i]].push_back(i);
  }
  vector<int> s(n);
  for (int i = 0; i < n; ++i) {
    for (int qi : open[i]) {
      upd(0, 0, q - 1, qi, v[qi]);
    }
    s[i] = qry(0, 0, q - 1, c[i]);
    for (int qi : close[i]) {
      upd(0, 0, q - 1, qi, 0);
    }
  }
  return s;
}

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