#include "candies.h"
#include <bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
//subtask 1
/*
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size();
std::vector<int> s(n);
int q = l.size();
for (int i = 0; i < q; i ++) {
for (int j = l[i]; j <= r[i]; j ++) {
s[j] = max(0, min(s[j] + v[i], c[j]));
}
}
return s;
}
*/
//subtask 2
/*
const int INF = 1e9 + 7;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size();
std::vector<int> s(n);
int q = l.size();
vector<long long> helper(n + 1);
for (int i = 0; i < q; i++) {
helper[l[i]] += v[i];
helper[r[i] + 1] -= v[i];
}
for (int i = 1; i < n; i++) {
helper[i] += helper[i - 1];
}
for (int i = 0; i < n; i++) {
s[i] = (int) (min(1LL * c[i], helper[i]));
}
return s;
}
*/
int find_mid(int l, int r) {
return l + r >> 1;
}
//subtask 3
struct Node {
pair<ll, int> ma;
pair<ll, int> mi;
ll lazy;
void apply(int val) {
ma.st += val;
mi.st += val;
lazy += val;
}
}node[4 * N];
void push(int id, int l, int r) {
if (l == r || node[id].lazy == 0) return;
int l_node = id << 1, r_node = id << 1 | 1;
int mid = find_mid(l, r);
node[l_node].apply(node[id].lazy);
node[r_node].apply(node[id].lazy);
node[id].lazy = 0;
}
void update(int id, int l, int r, int up_l, int up_r, int val) {
if (l > up_r || r < up_l) return;
push(id, l, r);
if (l >= up_l && r <= up_r) {
node[id].apply(val);
return;
}
int mid = find_mid(l, r), l_node = id << 1, r_node = id << 1 | 1;
update(l_node, l , mid, up_l, up_r, val);
update(r_node, mid + 1, r, up_l, up_r, val);
node[id].ma = (node[l_node].ma.st > node[r_node].ma.st) ? node[l_node].ma : node[r_node].ma;
node[id].mi = (node[l_node].mi.st < node[r_node].mi.st) ? node[l_node].mi : node[r_node].mi;
return;
}
ll query_sum(int id, int l, int r, int pos) {
push(id, l, r);
if (l == pos && r == pos) return node[id].ma.st;
int mid = find_mid(l, r), l_node = id << 1, r_node = id << 1 | 1;
if (mid >= pos) return query_sum(l_node, l, mid, pos);
else return query_sum(r_node, mid +1, r, pos);
}
pair<pair<ll, int>, pair<ll, int>> max_excluded(int id, int l, int r, ll val, ll ma, ll mi) {
push(id, l, r);
if ((l ==r) || max(node[id].ma.st, ma) - min(node[id].mi.st, mi) < val) return make_pair(node[id].ma, node[id].mi);
int mid = find_mid(l, r), l_node = id << 1, r_node = id << 1 | 1;
pair<pair<ll,int>, pair<ll,int>> p = max_excluded(r_node, mid +1, r, val, ma, mi);
ma = max(p.st.st, ma), mi = min(p.nd.st, mi);
if (ma - mi >= val) return p;
pair<pair<ll,int>, pair<ll,int>> q = max_excluded(l_node, l, mid, val, ma, mi);
if (q.st.st > p.st.st) p.st = q.st;
if (q.nd.st < p.nd.st) p.nd = q.nd;
return p;
}
void init(int id, int l, int r) {
node[id].ma = node[id].mi = make_pair(0, r);
node[id].lazy = 0;
if (l == r) return;
int mid = find_mid(l, r), l_node = id << 1, r_node = id << 1 | 1;
init(l_node, l, mid), init(r_node, mid +1, r);
return;
}
struct Event {
int pos;
int val;
int ord;
bool operator < (const Event &o) const {
return pos < o.pos;
}
Event (int pos, int val, int ord) : pos(pos), val(val), ord(ord){}
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
vector<Event> events;
for (int i = 0; i < l.size(); i++) {
events.emplace_back(l[i], v[i], i +1);
events.emplace_back(r[i] +1, -v[i], i +1);
}
sort(events.begin(), events.end());
int pt = 0, n = c.size(), m = v.size();
vector<int> ans(n);
init(1, 0, m);
for (int i = 0; i < n; i++) {
int val = c[i];
for (;pt < events.size() && events[pt].pos == i; pt++) {
update(1, 0, m, events[pt].ord, m,events[pt].val);
}
pair<pair<ll, int>, pair<ll, int>> mx = max_excluded(1, 0, m, 1ll * val, node[1].mi.st, node[1].ma.st);
if (mx.st.st - mx.nd.st < val) {
ans[i] = (int) query_sum(1, 0, m, m);
if (mx.nd.st < 0) {
ans[i] -= (int) query_sum(1, 0, m, mx.nd.nd);
}
} else {
int mx_pos = max(mx.st.nd, mx.nd.nd);
// fprintf(stderr, "at %d max_pos = %d\n", i, mx_pos);
ans[i] = mx_pos == mx.st.nd ? val : 0;
if (mx_pos < m) {
ans[i] += (int) (query_sum(1, 0, m, m) - query_sum(1, 0, m, mx_pos));
}
}
// for (int j = 0; j <= m; j++) fprintf(stderr, "%lld ", query_sum(1, 0, m, j));
// fprintf(stderr, "\n");
}
return ans;
}
Compilation message
candies.cpp: In function 'int find_mid(int, int)':
candies.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | return l + r >> 1;
| ~~^~~
candies.cpp: In function 'void push(int, int, int)':
candies.cpp:66:9: warning: unused variable 'mid' [-Wunused-variable]
66 | int mid = find_mid(l, r);
| ^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (int i = 0; i < l.size(); i++) {
| ~~^~~~~~~~~~
candies.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (;pt < events.size() && events[pt].pos == i; pt++) {
| ~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
31572 KB |
Output is correct |
| 2 |
Correct |
13 ms |
31516 KB |
Output is correct |
| 3 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 4 |
Correct |
14 ms |
31728 KB |
Output is correct |
| 5 |
Correct |
15 ms |
31752 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
395 ms |
48924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
31516 KB |
Output is correct |
| 2 |
Incorrect |
305 ms |
45584 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
31572 KB |
Output is correct |
| 2 |
Correct |
13 ms |
31544 KB |
Output is correct |
| 3 |
Correct |
142 ms |
45204 KB |
Output is correct |
| 4 |
Correct |
86 ms |
35392 KB |
Output is correct |
| 5 |
Correct |
256 ms |
47676 KB |
Output is correct |
| 6 |
Correct |
245 ms |
48352 KB |
Output is correct |
| 7 |
Incorrect |
231 ms |
48872 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
31572 KB |
Output is correct |
| 2 |
Correct |
13 ms |
31516 KB |
Output is correct |
| 3 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 4 |
Correct |
14 ms |
31728 KB |
Output is correct |
| 5 |
Correct |
15 ms |
31752 KB |
Output is correct |
| 6 |
Incorrect |
395 ms |
48924 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
