oj.uz

Submission #579598

# Submission time Handle Problem Language Result Execution time Memory
579598 2022-06-19T12:55:13 Z xyz Distributing Candies (IOI21_candies) C++17
100 / 100
 2109 ms 52560 KB 
#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;
                  debug(l, r, getmax(1, 0, q - 1, m) - getmin(1, 0, q - 1, m));
                  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;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 123
      |                    ^~~
candies.cpp:134:19: note: in expansion of macro 'debug'
  134 |                   debug(l, r, getmax(1, 0, q - 1, m) - getmin(1, 0, q - 1, m));
      |                   ^~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 9 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1661 ms 45920 KB Output is correct
2 Correct 1746 ms 49944 KB Output is correct
3 Correct 1781 ms 49824 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 373 ms 31456 KB Output is correct
3 Correct 809 ms 16296 KB Output is correct
4 Correct 1942 ms 51780 KB Output is correct
5 Correct 2109 ms 52240 KB Output is correct
6 Correct 1920 ms 52560 KB Output is correct
7 Correct 1867 ms 51896 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 137 ms 31068 KB Output is correct
4 Correct 702 ms 15096 KB Output is correct
5 Correct 1222 ms 44320 KB Output is correct
6 Correct 1179 ms 45140 KB Output is correct
7 Correct 1068 ms 45648 KB Output is correct
8 Correct 1238 ms 44256 KB Output is correct
9 Correct 1495 ms 45756 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 9 ms 724 KB Output is correct
6 Correct 1661 ms 45920 KB Output is correct
7 Correct 1746 ms 49944 KB Output is correct
8 Correct 1781 ms 49824 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 373 ms 31456 KB Output is correct
11 Correct 809 ms 16296 KB Output is correct
12 Correct 1942 ms 51780 KB Output is correct
13 Correct 2109 ms 52240 KB Output is correct
14 Correct 1920 ms 52560 KB Output is correct
15 Correct 1867 ms 51896 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 137 ms 31068 KB Output is correct
19 Correct 702 ms 15096 KB Output is correct
20 Correct 1222 ms 44320 KB Output is correct
21 Correct 1179 ms 45140 KB Output is correct
22 Correct 1068 ms 45648 KB Output is correct
23 Correct 1238 ms 44256 KB Output is correct
24 Correct 1495 ms 45756 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 743 ms 15196 KB Output is correct
27 Correct 336 ms 30932 KB Output is correct
28 Correct 1760 ms 50388 KB Output is correct
29 Correct 1659 ms 50932 KB Output is correct
30 Correct 1639 ms 51112 KB Output is correct
31 Correct 1637 ms 51208 KB Output is correct
32 Correct 1588 ms 51420 KB Output is correct