| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1242803 | santi3223 | 사탕 분배 (IOI21_candies) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
//#include "candies.h"
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < (ll)cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
ll n = c.size();
std::vector<int> s(n, 0);
if(n <= 2000 && l.size() <= 2000){
ff(x, 0, l.size()){
if(v[x] == 0){
continue;
}
ff(i, l[x], r[x]+1){
if(v[x] > 0){
s[i] = min(c[i], s[i]+v[x]);
}
else{
s[i] = max(0, s[i]+v[x]);
}
}
}
return s;
}
vector<int> pref(n, 0);
ff(x, 0, l.size()){
pref[l[x]] += v[x];
if(r[x]+1 < n){
pref[r[x]+1] += -v[x];
}
/*cout << l[x] << " " << r[x]+1 << " " << v[x] << ed;
ff(i, 0, n){
cout << pref[i] << " ";
}
cout << ed << ed;*/
}
ff(i, 1, n){
pref[i] += pref[i-1];
}
ff(i, 0, n){
s[i] = min(c[i], pref[i]);
}
return s;
}
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;
}