Submission #579596

#	Time	Username	Problem	Language	Result	Execution time	Memory
579596		xyz	Distributing Candies (IOI21_candies)	C++17	0 / 100	1645 ms	50716 KiB

candies

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

#ifdef LOCAL
#include "../debug.h"
#else
#define debug(...) 123
#endif

const int N = 2e5 + 20;
const ll inf = 1e17;

ll xtime[4 * N], mx[4 * N], mn[4 * N], push[4 * N];
ll u[N];

void makepush(int v){
      if(!push[v])
            return;
      mx[v * 2] += push[v];
      mn[v * 2] += push[v];
      mx[v * 2 + 1] += push[v];
      mn[v * 2 + 1] += push[v];
      push[v * 2] += push[v];
      push[v * 2 + 1] += push[v];
      push[v] = 0;
}

void modify_value(int v, int tl, int tr, int l, int r, int x){
      if(l > r)
            return;
      if(tl == l && tr == r){
            mx[v] += x;
            mn[v] += x;
            push[v] += x;
            return;
      }
      makepush(v);
      int tm = (tl + tr) / 2;
      modify_value(v * 2, tl, tm, l, min(r, tm), x);
      modify_value(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, x);
      mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
      mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
}

void modify_time(int v, int tl, int tr, int pos, int x){
      if(tl == tr){
            xtime[v] += x;
            return;
      }
      int tm = (tl + tr) / 2;
      if(pos <= tm)
            modify_time(v * 2, tl, tm, pos, x);
      else
            modify_time(v * 2 + 1, tm + 1, tr, pos, x);
      xtime[v] = xtime[v * 2] + xtime[v * 2 + 1];
}

ll getmax(int v, int tl, int tr, ll t){
      if(xtime[v] < t){
            return -inf;
      }
      if(!t)
            return mx[v];
      if(tl == tr){
            return mx[v] - u[tl] + (u[tl] > 0 ? xtime[v] : -t);
      }
      makepush(v);
      int tm = (tl + tr) / 2;
      if(xtime[v * 2] >= t){
            return max(getmax(v * 2, tl, tm, t), mx[v * 2 + 1]);
      }else{
            return getmax(v * 2 + 1, tm + 1, tr, t - xtime[v * 2]);
      }
}

ll getmin(int v, int tl, int tr, ll t){
      if(xtime[v] < t){
            return inf;
      }
      if(!t)
            return mn[v];
      if(tl == tr){
            return mn[v] - u[tl] + (u[tl] > 0 ? t : -xtime[v]);
      }
      makepush(v);
      int tm = (tl + tr) / 2;
      if(xtime[v * 2] >= t){
            return min(getmin(v * 2, tl, tm, t), mn[v * 2 + 1]);
      }else{
            return getmin(v * 2 + 1, tm + 1, tr, t - xtime[v * 2]);
      }
}

vector<int> distribute_candies(vector<int> c, vector<int> lx, vector<int> rx, vector<int> vx) {
      int n = c.size();
      vector<tuple<int, int, int>> md;
      md.emplace_back(0, n - 1, -1e9);
      md.emplace_back(0, n - 1, +1e9);
      vector<ll> bal(n + 1);
      vector<vector<int>> open(n + 1), close(n + 1);
      int q = lx.size();
      for(int i = 0; i < q; i ++){
            md.emplace_back(lx[i], rx[i], vx[i]);
            bal[lx[i]] += vx[i];
            bal[rx[i]+1] -= vx[i];
      }
      q = md.size();
      for(int i = 0; i < q; i ++){
            open[get<0>(md[i])].emplace_back(i);
            close[get<1>(md[i]) + 1].emplace_back(i);
      }
      for(int i = 0; i < q; i ++)
            u[i] = get<2>(md[i]);
      ll sum = 0;
      for(int i = 0; i < n; i ++){
            sum += bal[i];
            bal[i] = sum;
      }
      vector<int> ans(n);
      for(int i = 0; i < n; i ++){
            for(int j : open[i]){
                  modify_value(1, 0, q - 1, j, q - 1, u[j]);
                  modify_time(1, 0, q - 1, j, abs(u[j]));
            }
            for(int j : close[i]){
                  modify_value(1, 0, q - 1, j, q - 1, -u[j]);
                  modify_time(1, 0, q - 1, j, -abs(u[j]));
            }
            ll l = 0, r = inf;
            while(l < r){
                  ll m = (l + r) / 2;
                  if(getmax(1, 0, q - 1, m) - getmin(1, 0, q - 1, m) > c[i])
                        l = m + 1;
                  else
                        r = m;
            }
            ans[i] = bal[i] - getmin(1, 0, q - 1, l);
      }
      return ans;
}

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