oj.uz

Submission #444627

# Submission time Handle Problem Language Result Execution time Memory
444627 2021-07-14T13:09:17 Z xyz Distributing Candies (IOI21_candies) C++17
30 / 100
 4682 ms 47172 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> l,
                               vector<int> r, vector<int> v) {
      vx = v;
      int n = c.size();
      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;
                  if(Max(1, 0, q - 1, mid) - Min(1, 0, q - 1, mid) > c[i])
                        l = mid + 1;
                  else
                        r = mid;
            }
            result[i] = max(0ll, total[i] - Min(1, 0, q - 1, l));
      }
      return result;
}

Subtask #1
3.0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3422 ms 46840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 604 ms 29276 KB Output is correct
3 Correct 2045 ms 14232 KB Output is correct
4 Correct 4599 ms 47148 KB Output is correct
5 Correct 4682 ms 47088 KB Output is correct
6 Correct 3927 ms 47172 KB Output is correct
7 Correct 3955 ms 47100 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 17 ms 748 KB Output is correct
6 Incorrect 3422 ms 46840 KB Output isn't correct
7 Halted 0 ms 0 KB -