#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "candies.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10;
vector <pair <int, int> > s[N];
struct node {
long long maxi, mini, sum;
} st[N * 4];
void add(int id, int L, int R, int i, int val) {
// cout << i << ' ' << val << "aaa\n";
if (L == R) {
st[id].maxi = max(val, 0);
st[id].mini = min(val, 0);
st[id].sum = val;
return;
}
int mid = L + R >> 1;
if (i <= mid) add(id * 2, L, mid, i, val);
else add(id * 2 + 1, mid + 1, R, i, val);
st[id].maxi = max(st[id * 2 + 1].maxi, st[id * 2 + 1].sum + st[id * 2].maxi);
st[id].mini = min(st[id * 2 + 1].mini, st[id * 2 + 1].sum + st[id * 2].mini);
st[id].sum = st[id * 2].sum + st[id * 2 + 1].sum;
}
tuple <long long, long long, long long, int> get(int id, int L, int R, int k, long long maxi, long long mini, long long sum) {
if (L == R) return make_tuple(max(maxi, st[id].maxi + sum), min(mini, st[id].mini + sum), sum, L);
int mid = L + R >> 1;
long long _maxi = max(maxi, st[id * 2 + 1].maxi + sum);
long long _mini = min(mini, st[id * 2 + 1].mini + sum);
long long _sum = sum + st[id * 2 + 1].sum;
if (_maxi - _mini > k) return get(id * 2 + 1, mid + 1, R, k, maxi, mini, sum);
else return get(id * 2, L, mid, k, _maxi, _mini, _sum);
}
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();
int q = v.size();
for (int i = 0; i < q; ++i) {
s[l[i]].push_back({v[i], i});
s[r[i] + 1].push_back({v[i], i + q});
}
vector <int> ans;
for (int i = 0; i < n; ++i) {
for (auto [x, id]: s[i]) {
if (id < q) add(1, 0, q - 1, id, x);
else add(1, 0, q - 1, id - q, 0);
// cout << id << ' ' << x << ' ' << st[1].sum << "aaaa\n";
// cout << x << ' ' << id << "aa\n";
}
// cout << st[1].sum << "-----\n";
auto [maxi, mini, sum, id] = get(1, 0, q - 1, c[i], 0, 0, 0);
// cout << maxi << ' ' << mini << " " << sum << "aa\n";
// cout << id << "aa\n";
if (maxi - mini <= c[i]) {
ans.push_back(st[1].sum);
} else {
if (v[id] < 0) {
ans.push_back(sum);
} else {
ans.push_back(c[i] + sum);
}
}
}
return ans;
}
//
//int main() {
// int n;
// assert(1 == scanf("%d", &n));
// std::vector<int> c(n);
// for(int i = 0; i < n; ++i) {
// assert(scanf("%d", &c[i]) == 1);
// }
//
// int q;
// assert(1 == scanf("%d", &q));
// std::vector<int> l(q), r(q), v(q);
// for(int i = 0; i < q; ++i) {
// assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
// }
//
// std::vector<int> ans = distribute_candies(c, l, r, v);
//
// for(int i = 0; i < n; ++i) {
// if (i > 0) {
// printf(" ");
// }
// printf("%d", ans[i]);
// }
// printf("\n");
// fclose(stdout);
// return 0;
//}
Compilation message
candies.cpp: In function 'void add(int, int, int, int, int)':
candies.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int mid = L + R >> 1;
| ~~^~~
candies.cpp: In function 'std::tuple<long long int, long long int, long long int, int> get(int, int, int, int, long long int, long long int, long long int)':
candies.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid = L + R >> 1;
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
362 ms |
34704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
5004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
