oj.uz

Submission #1026887

# Submission time Handle Problem Language Result Execution time Memory
1026887 2024-07-18T12:59:50 Z NeroZein Distributing Candies (IOI21_candies) C++17
100 / 100
 235 ms 39956 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std; 

const int N = 2e5 + 5; 

struct node {
  long long sum = 0, min_pref = 0, max_pref = 0; 
}; 

node combine(node lx, node rx) {
  node ret;
  ret.sum = lx.sum + rx.sum;
  ret.min_pref = min(lx.min_pref, lx.sum + rx.min_pref);
  ret.max_pref = max(lx.max_pref, lx.sum + rx.max_pref);
  return ret;
}

node seg[N * 2]; 

void upd(int nd, int l, int r, int p, int v) {
  if (l == r) {
    seg[nd].sum = v;
    seg[nd].min_pref = min(0, v);
    seg[nd].max_pref = max(0, v);
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    upd(nd + 1, l, mid, p, v);
  } else {
    upd(rs, mid + 1, r, p, v); 
  }
  seg[nd] = combine(seg[nd + 1], seg[rs]);
}

int qry(int nd, int l, int r, int c) {
  if (l == r) {
    return max(0LL, min((long long) c, seg[nd].sum)); 
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1); 
  if (seg[rs].max_pref - seg[rs].min_pref >= c) {
    return qry(rs, mid + 1, r, c); 
  }
  int ret = qry(nd + 1, l, mid, c); 
  if (ret + seg[rs].min_pref <= 0) {
    ret = seg[rs].sum - seg[rs].min_pref;
  } else if (ret + seg[rs].max_pref >= c) {
    ret = c + (seg[rs].sum - seg[rs].max_pref);
  } else {
    ret += seg[rs].sum;
  }
  return ret; 
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
  int n = (int) c.size();
  int q = (int) l.size();
  vector<vector<int>> open(n);
  vector<vector<int>> close(n);
  for (int i = 0; i < q; ++i) {
    open[l[i]].push_back(i);
    close[r[i]].push_back(i);
  }
  vector<int> s(n);
  for (int i = 0; i < n; ++i) {
    for (int qi : open[i]) {
      upd(0, 0, q - 1, qi, v[qi]);
    }
    s[i] = qry(0, 0, q - 1, c[i]);
    for (int qi : close[i]) {
      upd(0, 0, q - 1, qi, 0);
    }
  }
  return s;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 38512 KB Output is correct
2 Correct 192 ms 37464 KB Output is correct
3 Correct 234 ms 37204 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 108 ms 20308 KB Output is correct
3 Correct 41 ms 14428 KB Output is correct
4 Correct 201 ms 39256 KB Output is correct
5 Correct 205 ms 39764 KB Output is correct
6 Correct 179 ms 39956 KB Output is correct
7 Correct 235 ms 39396 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 77 ms 18876 KB Output is correct
4 Correct 37 ms 13404 KB Output is correct
5 Correct 126 ms 31532 KB Output is correct
6 Correct 118 ms 32192 KB Output is correct
7 Correct 121 ms 32704 KB Output is correct
8 Correct 143 ms 31424 KB Output is correct
9 Correct 126 ms 32812 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 202 ms 38512 KB Output is correct
7 Correct 192 ms 37464 KB Output is correct
8 Correct 234 ms 37204 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 108 ms 20308 KB Output is correct
11 Correct 41 ms 14428 KB Output is correct
12 Correct 201 ms 39256 KB Output is correct
13 Correct 205 ms 39764 KB Output is correct
14 Correct 179 ms 39956 KB Output is correct
15 Correct 235 ms 39396 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 77 ms 18876 KB Output is correct
19 Correct 37 ms 13404 KB Output is correct
20 Correct 126 ms 31532 KB Output is correct
21 Correct 118 ms 32192 KB Output is correct
22 Correct 121 ms 32704 KB Output is correct
23 Correct 143 ms 31424 KB Output is correct
24 Correct 126 ms 32812 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 44 ms 13636 KB Output is correct
27 Correct 109 ms 20048 KB Output is correct
28 Correct 178 ms 37944 KB Output is correct
29 Correct 199 ms 38404 KB Output is correct
30 Correct 177 ms 38484 KB Output is correct
31 Correct 180 ms 38744 KB Output is correct
32 Correct 196 ms 38996 KB Output is correct