oj.uz

Submission #444638

# Submission time Handle Problem Language Result Execution time Memory
444638 2021-07-14T13:29:56 Z xyz Distributing Candies (IOI21_candies) C++17
100 / 100
 4853 ms 49344 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 19 ms 772 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3475 ms 49204 KB Output is correct
2 Correct 3803 ms 49284 KB Output is correct
3 Correct 3989 ms 49344 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 531 ms 31656 KB Output is correct
3 Correct 1996 ms 14012 KB Output is correct
4 Correct 4545 ms 49196 KB Output is correct
5 Correct 4853 ms 49188 KB Output is correct
6 Correct 4016 ms 49344 KB Output is correct
7 Correct 4046 ms 49212 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 188 ms 29656 KB Output is correct
4 Correct 1569 ms 13892 KB Output is correct
5 Correct 2885 ms 42808 KB Output is correct
6 Correct 2558 ms 42932 KB Output is correct
7 Correct 2631 ms 42936 KB Output is correct
8 Correct 3037 ms 43060 KB Output is correct
9 Correct 3769 ms 42932 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 19 ms 772 KB Output is correct
6 Correct 3475 ms 49204 KB Output is correct
7 Correct 3803 ms 49284 KB Output is correct
8 Correct 3989 ms 49344 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 531 ms 31656 KB Output is correct
11 Correct 1996 ms 14012 KB Output is correct
12 Correct 4545 ms 49196 KB Output is correct
13 Correct 4853 ms 49188 KB Output is correct
14 Correct 4016 ms 49344 KB Output is correct
15 Correct 4046 ms 49212 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 4 ms 332 KB Output is correct
18 Correct 188 ms 29656 KB Output is correct
19 Correct 1569 ms 13892 KB Output is correct
20 Correct 2885 ms 42808 KB Output is correct
21 Correct 2558 ms 42932 KB Output is correct
22 Correct 2631 ms 42936 KB Output is correct
23 Correct 3037 ms 43060 KB Output is correct
24 Correct 3769 ms 42932 KB Output is correct
25 Correct 0 ms 332 KB Output is correct
26 Correct 1839 ms 14008 KB Output is correct
27 Correct 512 ms 31664 KB Output is correct
28 Correct 3732 ms 49344 KB Output is correct
29 Correct 3566 ms 49204 KB Output is correct
30 Correct 3531 ms 49188 KB Output is correct
31 Correct 3479 ms 49196 KB Output is correct
32 Correct 3393 ms 49304 KB Output is correct