## Submission #1084139

# Submission time Handle Problem Language Result Execution time Memory
1084139 2024-09-05T10:36:21 Z steveonalex Distributing Candies (IOI21_candies) C++17
32 / 100
603 ms 42860 KB
```#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define ALL(v) (v).begin(), (v).end()
#define block_of_code if(true)

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
double rngesus_d(double l, double r){
double cur = rngesus(0, MASK(60) - 1);
return l + cur * (r - l);
}

template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}

template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}

template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}

template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}

struct SegmentTree{
struct Node{
ll l, r, lazy;
Node(){l = r = lazy = 0;}
};

int n;
vector<Node> a;

SegmentTree(int _n){
n = _n;
a.resize(n * 4 + 8);
}

void update_node(int i, int v){
a[i].l += v; a[i].r += v; a[i].lazy += v;
}

void merge_child(int id){
a[id].l = min(a[id * 2].l, a[id * 2 + 1].l);
a[id].r = max(a[id * 2].r, a[id * 2 + 1].r);
}

void down(int id){
update_node(id * 2, a[id].lazy); update_node(id * 2 + 1, a[id].lazy);
a[id].lazy = 0;
}

void update(int u, int v, int val, int l, int r, int id){
if (u <= l && r <= v){
update_node(id, val);
return;
}
if (a[id].lazy) down(id);
int mid = (l + r) >> 1;
if (u <= mid) update(u, v, val, l, mid, id * 2);
if (v > mid) update(u, v, val, mid + 1, r, id * 2 + 1);
merge_child(id);
}

void update(int u, int v, int val){
update(u, v, val, 0, n, 1);
}

pair<ll, ll> combine_range(pair<ll, ll> a, pair<ll, ll> b){
return make_pair(min(a.first, b.first), max(a.second, b.second));
}

pair<ll, ll> get(int u, int v, int l, int r, int id){
if (u <= l && r <= v) return make_pair(a[id].l, a[id].r);
if (a[id].lazy) down(id);
int mid = (l + r) >> 1;
pair<ll, ll> ans = {1e18, -1e18};
if (u <= mid) ans = combine_range(ans, get(u, v, l, mid, id * 2));
if (v > mid) ans = combine_range(ans, get(u, v, mid + 1, r, id * 2 + 1));
return ans;
}

pair<ll, ll> get(int u, int v){
return get(u, v, 0, n, 1);
}
};

vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
int n = c.size(), q = l.size();
SegmentTree st(q);
vector<vector<pair<int, int>>> queries(n+1);
for(int i = 0; i<q; ++i){
queries[l[i]].push_back({i + 1, v[i]});
queries[r[i]+1].push_back({i + 1, -v[i]});
}

vector<int> a(n);
ll sum = 0;
for(int i = 0; i<n; ++i){
for(pair<int, int> j: queries[i]){
st.update(j.first, q, j.second);
sum += j.second;
}
pair<ll, ll> cur = st.get(0, q);
if (cur.second - cur.first <= c[i]){
a[i] = sum - cur.first;
}
else{
int l = 1, r = q;
while(l < r){
int mid = (l + r) >> 1;
pair<ll, ll> cur = st.get(mid, q);
if (cur.second - cur.first <= c[i]) r = mid;
else l = mid + 1;
}
pair<ll, ll> cur = st.get(l, q);
int x = l - 1;
if (v[x] > 0){
a[i] = c[i] - (cur.second - sum);
}
else a[i] = sum - cur.first;
}
}

return a;
}

```

#### 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 3 ms 860 KB Output is correct

#### Subtask #2 0 / 8.0

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

#### Subtask #3 0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 176 ms 31312 KB Output isn't correct
3 Halted 0 ms 0 KB -

#### Subtask #4 29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 82 ms 29984 KB Output is correct
4 Correct 125 ms 8792 KB Output is correct
5 Correct 322 ms 37556 KB Output is correct
6 Correct 362 ms 38072 KB Output is correct
7 Correct 391 ms 38832 KB Output is correct
8 Correct 324 ms 37536 KB Output is correct
9 Correct 407 ms 38840 KB Output is correct

#### Subtask #5 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 3 ms 860 KB Output is correct
6 Incorrect 603 ms 42860 KB Output isn't correct
7 Halted 0 ms 0 KB -