//Challenge: Accepted
#include "candies.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b) {
cout << a << " ", debug(b ...);
};
template<class T> void pary (T l, T r) {
while (l!= r) cout << *l << " ", l++;
cout << endl;
};
#define ll long long
#define maxn 200005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size(), q = v.size();
vector<int> ret(n, 0);
vector<pii> seg;
for (int i = 0;i < q;i++) {
if (v[i] >= 0) {
while (seg.size() && seg.back().ss <= v[i]) {
seg.pop_back();
}
if (seg.size() && seg.back().ff <= v[i]) {
seg.back().ff = 0;
} else {
seg.push_back({0, v[i]});
}
} else {
v[i] = -v[i];
int cur = 0;
while (seg.size() && cur < v[i]) {
if (cur + seg.back().ss - seg.back().ff <= v[i]) {
cur += seg.back().ss - seg.back().ff;
seg.pop_back();
} else {
seg.back().ff += v[i] - cur;
cur = v[i];
break;
}
}
}
//for (auto p:seg) debug(p.ff, p.ss);
//debug();
}
vector<pii> a(n);
for (int i = 0;i < n;i++) a[i] = {c[i], i};
sort(a.begin(), a.end());
reverse(seg.begin(), seg.end());
int ind = 0, sum = 0;
for (int i = 0;i < n;i++) {
bool type = 0;
while (ind < seg.size() && seg[ind].ff <= a[i].ff) {
if (seg[ind].ss <= a[i].ff) {
sum += seg[ind].ss - seg[ind].ff;
ind++;
} else {
type = 1;
ret[a[i].ss] = sum + a[i].ff - seg[ind].ff;
break;
}
}
if (!type) ret[a[i].ss] = sum;
}
return ret;
}
/*
5
0 3 6 8 9
5
0 4 4
0 4 -2
0 4 7
0 4 -3
0 4 -2
*/
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:60:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | while (ind < seg.size() && seg[ind].ff <= a[i].ff) {
| ~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
113 ms |
10612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
