oj.uz

Submission #444635

# Submission time Handle Problem Language Result Execution time Memory
444635 2021-07-14T13:25:55 Z xyz Distributing Candies (IOI21_candies) C++17
100 / 100
 4909 ms 50916 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 = 1e18;
            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 1 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 776 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3570 ms 49196 KB Output is correct
2 Correct 3662 ms 49212 KB Output is correct
3 Correct 3695 ms 49216 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 538 ms 31652 KB Output is correct
3 Correct 2078 ms 14004 KB Output is correct
4 Correct 4708 ms 49212 KB Output is correct
5 Correct 4909 ms 49200 KB Output is correct
6 Correct 4141 ms 49204 KB Output is correct
7 Correct 4135 ms 49208 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 3 ms 400 KB Output is correct
3 Correct 241 ms 29668 KB Output is correct
4 Correct 1699 ms 13896 KB Output is correct
5 Correct 3030 ms 42956 KB Output is correct
6 Correct 3015 ms 42936 KB Output is correct
7 Correct 2469 ms 42948 KB Output is correct
8 Correct 2808 ms 42936 KB Output is correct
9 Correct 3979 ms 42944 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 776 KB Output is correct
6 Correct 3570 ms 49196 KB Output is correct
7 Correct 3662 ms 49212 KB Output is correct
8 Correct 3695 ms 49216 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 538 ms 31652 KB Output is correct
11 Correct 2078 ms 14004 KB Output is correct
12 Correct 4708 ms 49212 KB Output is correct
13 Correct 4909 ms 49200 KB Output is correct
14 Correct 4141 ms 49204 KB Output is correct
15 Correct 4135 ms 49208 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 3 ms 400 KB Output is correct
18 Correct 241 ms 29668 KB Output is correct
19 Correct 1699 ms 13896 KB Output is correct
20 Correct 3030 ms 42956 KB Output is correct
21 Correct 3015 ms 42936 KB Output is correct
22 Correct 2469 ms 42948 KB Output is correct
23 Correct 2808 ms 42936 KB Output is correct
24 Correct 3979 ms 42944 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1787 ms 15212 KB Output is correct
27 Correct 546 ms 33340 KB Output is correct
28 Correct 3864 ms 50800 KB Output is correct
29 Correct 3650 ms 50816 KB Output is correct
30 Correct 3677 ms 50800 KB Output is correct
31 Correct 3528 ms 50916 KB Output is correct
32 Correct 3466 ms 50816 KB Output is correct