Submission #444638

#	Time	Username	Problem	Language	Result	Execution time	Memory
444638		xyz	Distributing Candies (IOI21_candies)	C++17	100 / 100	4853 ms	49344 KiB

candies

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

const int N = 2e5 + 200;
const ll inf = 1e18;

ll Time[4 * N], maxPref[4 * N], minPref[4 * N], push[4 * N], pref[4 * N];
vector<int> vx;
int q;

void makepush(int v, int tl, int tr){
      if(tl == tr || !push[v])
            return;
      maxPref[v * 2] += push[v];
      minPref[v * 2] += push[v];
      push[v * 2] += push[v];
      pref[v * 2] += push[v];
      maxPref[v * 2 + 1] += push[v];
      minPref[v * 2 + 1] += push[v];
      push[v * 2 + 1] += push[v];
      pref[v * 2 + 1] += push[v];
      push[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r, ll x){
      if(l > r)
            return;
      if(tl == l && tr == r){
            maxPref[v] += x;
            minPref[v] += x;
            pref[v] += x;
            push[v] += x;
            return;
      }
      makepush(v, tl, tr);
      int tm = (tl + tr) / 2;
      upd(v * 2, tl, tm, l, min(r, tm), x);
      upd(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, x);
      maxPref[v] = max(maxPref[v * 2], maxPref[v * 2 + 1]);
      minPref[v] = min(minPref[v * 2], minPref[v * 2 + 1]);
}

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

ll getPref(int v, int tl, int tr, int pos){
      if(pos < 0) return 0;
      makepush(v, tl, tr);
      if(tl == tr){
            return pref[v];
      }
      int tm = (tl + tr) / 2;
      if(pos <= tm)
            return getPref(v * 2, tl, tm, pos);
      else
            return getPref(v * 2 + 1, tm + 1, tr, pos);
}

ll Max(int v, int tl, int tr, ll T){ // [T, +oo)
      makepush(v, tl, tr);
      if(Time[v] < T)
            return -inf;
      if(!T)
            return maxPref[v];
      if(tl == tr){
            if(Time[v] < T)
                  return -inf;
            return getPref(1, 0, q - 1, tl - 1) + max((vx[tl] > 0 ? +1ll : -1ll) * T, (vx[tl] > 0 ? +1ll : -1ll) * Time[v]);
      }
      int tm = (tl + tr) / 2;
      if(Time[v * 2] >= T)
            return max(Max(v * 2, tl, tm, T), maxPref[v * 2 + 1]);
      else
            return Max(v * 2 + 1, tm + 1, tr, T - Time[v * 2]);
}


ll Min(int v, int tl, int tr, ll T){ // [T, +oo)
      makepush(v, tl, tr);
      if(Time[v] < T)
            return -inf;
      if(!T)
            return minPref[v];
      if(tl == tr){
            if(Time[v] < T)
                  return -inf;
            return getPref(1, 0, q - 1, tl - 1) + min((vx[tl] > 0 ? +1ll : -1ll) * T, (vx[tl] > 0 ? +1ll : -1ll) * Time[v]);
      }
      int tm = (tl + tr) / 2;
      if(Time[v * 2] >= T)
            return min(Min(v * 2, tl, tm, T), minPref[v * 2 + 1]);
      else
            return Min(v * 2 + 1, tm + 1, tr, T - Time[v * 2]);
}

vector<int> distribute_candies(vector<int> c, vector<int> llx,
                               vector<int> rrx, vector<int> vvx) {
      int n = c.size();
      vector<int> l, r, v;
      l.push_back(0);
      r.push_back(n - 1);
      v.push_back(1e9);
      l.push_back(0);
      r.push_back(n - 1);
      v.push_back(-1e9);
      for(int e : llx) l.push_back(e);
      for(int e : rrx) r.push_back(e);
      for(int e : vvx) v.push_back(e);

      vx = v;
      q = l.size();
      vector<ll> total(n);
      for(int i = 0; i < q; i ++){
            total[l[i]] += v[i];
            if(r[i] + 1 < n)
                  total[r[i] + 1] -= v[i];
      }
      ll bal = 0;
      for(int i = 0; i < n; i ++){
            bal += total[i];
            total[i] = bal;
      }
      vector<int> Add[n], Remove[n];
      for(int i = 0; i < q; i ++){
            Add[l[i]].push_back(i);
            if(r[i] + 1 < n)
                  Remove[r[i] + 1].push_back(i);
      }
      vector<int> result(n);
      for(int i = 0; i < n; i ++){
            for(int x : Add[i])
                  upd(1, 0, q - 1, x, q - 1, v[x]),
                  updTime(1, 0, q - 1, x, abs(v[x]));
            for(int x : Remove[i])
                  upd(1, 0, q - 1, x, q - 1, -v[x]),
                  updTime(1, 0, q - 1, x, -abs(v[x]));
            ll l = 0, r = 1e16;
            while(l < r){
                  ll mid = (l + r) / 2;
//                  cout << l << " " << r << " : " << Max(1, 0, q - 1, mid) - Min(1, 0, q - 1, mid) << endl;
                  if(Max(1, 0, q - 1, mid) - Min(1, 0, q - 1, mid) > c[i])
                        l = mid + 1;
                  else
                        r = mid;
            }
//            cout << l << endl;
//            cout << Min(1, 0, q - 1, l) << endl;
            result[i] = max(0ll, total[i] - Min(1, 0, q - 1, l));
      }
      return result;
}

//
//1 1000
//1
//0 0 100

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