| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 615429 |
2022-07-31T09:08:40 Z |
박상훈(#8491) |
Ants and Sugar (JOI22_sugar) |
C++17 |
|
531 ms |
45808 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node{
ll l, r, ans, ansl, ansr, anslr;
Node(){}
Node(ll _l, ll _r, ll _prf, ll _suf, ll _ran, ll _sum): l(_l), r(_r), ans(_prf), ansl(_suf), ansr(_ran), anslr(_sum) {}
Node operator + (const Node &N) const{
Node ret;
ret.l = l;
ret.r = N.r;
ret.ans = min(min(ans, N.ans), ans+N.ans);
ret.ans = min(ret.ans, ansr+N.ansl-r);
ret.ansl = min(ansl, min(ansl+N.ans, anslr+N.ansl-r));
ret.ansr = min(N.ansr, min(N.ansr+ans, N.anslr+ansr-r));
ret.anslr = min(ansl+N.ansr, anslr+N.anslr-r);
/*ret.prf = min(prf, sum + N.prf - r);
ret.suf = min(N.suf, N.sum + suf - r);
ret.ran = min(suf + N.prf - r, min(ran, N.ran));
ret.sum = sum + N.sum - r;*/
return ret;
}
};
struct Seg{
Node tree[1201200];
void init(int i, int l, int r){
tree[i] = Node(0, 0, 0, 0, 0, 0);
if (l==r) return;
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
}
void update(int i, int l, int r, int s, int x){
if (r<s || s<l) return;
if (l==r){
tree[i].ans -= x;
tree[i].ansl -= x;
tree[i].ansr -= x;
tree[i].anslr -= x;
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, x); update(i<<1|1, m+1, r, s, x);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
void update2(int i, int l, int r, int s, int e, int x){
if (r<s || e<l) return;
if (l==r){
tree[i].ans += x;
tree[i].ansl += x;
tree[i].ansr += x;
tree[i].anslr += x;
if (l==s){
tree[i].r += x;
}
if (l==e){
tree[i].l += x;
}
return;
}
int m = (l+r)>>1;
update2(i<<1, l, m, s, e, x); update2(i<<1|1, m+1, r, s, e, x);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
}tree;
ll a[1010101];
ll naive(int n){
ll ret = 0;
for (int i=1;i<=n;i++){
for (int j=i;j<=n;j++) if (i%2==1 && j%2==1){
ll tmp = 0;
for (int k=i-1;k<=j+1;k++){
if (k%2==0) tmp += a[k];
else tmp -= a[k];
}
ret = min(ret, tmp);
}
}
return ret;
}
int main(){
int n, d;
scanf("%d %d", &n, &d);
tree.init(1, 1, n/2+2);
ll S = 0;
for (int i=1;i<=n;i++){
int op, x, y;
scanf("%d %d %d", &op, &x, &y);
a[x] += y;
if (x%2==1){
S += y;
tree.update(1, 1, n/2+2, (x+1)/2, y);
}
else{
tree.update2(1, 1, n/2+2, x/2, x/2+1, y);
}
ll tmp = min(tree.tree[1].ans, 0LL);
//ll tmp2 = naive(n);
printf("%lld\n", S + tmp);
}
}
/*
void solve(vector<pair<int, int>> A[], int d){
sort(A[0].begin(), A[0].end());
sort(A[1].begin(), A[1].end());
A[0].emplace_back(2e9, 0);
A[1].emplace_back(2e9, 0);
deque<pair<int, int>> dq;
int typ = 0, pt[2] = {0, 0};
ll ans = 0;
while(pt[0]<(int)A[0].size()-1 || pt[1]<(int)A[1].size()-1){
int cur = 0;
if (A[0][pt[0]].first > A[1][pt[1]].first) cur = 1;
if (typ==cur){
dq.push_back(A[cur][pt[cur]]);
pt[cur]++;
}
else{
auto p = A[cur][pt[cur]];
while(!dq.empty()){
if (p.first - dq.front().first > d) {dq.pop_front(); continue;}
ans += min(p.second, dq.front().second);
//printf("%d %d -> %d\n", p.first, dq.front().first, min(p.second, dq.front().second));
if (p.second >= dq.front().second){
p.second -= dq.front().second;
dq.pop_front();
}
else{
dq.front().second -= p.second;
p.second = 0;
}
if (p.second == 0) {printf("ok %d %d\n", p.first, p.second);break; }
}
//printf(" %d %d\n", p.first, p.second);
if (p.second > 0){
//printf("YES %d %d\n", p.first, p.second);
assert(dq.empty());
typ = cur;
dq.push_back(p);
}
pt[cur]++;
}
}
A[0].pop_back();
A[1].pop_back();
printf("%lld\n", ans);
}
int main(){
int n, d;
scanf("%d %d", &n, &d);
vector<pair<int, int>> A[2];
for (int i=1;i<=n;i++){
int t, x, y;
scanf("%d %d %d", &t, &x, &y);
A[t-1].emplace_back(x, y);
solve(A, d);
}
return 0;
}
*/
Compilation message
sugar.cpp: In function 'int main()':
sugar.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d %d", &n, &d);
| ~~~~~^~~~~~~~~~~~~~~~~
sugar.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d %d %d", &op, &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
316 KB |
Output is correct |
| 2 |
Correct |
0 ms |
308 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
308 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
376 ms |
39492 KB |
Output is correct |
| 5 |
Correct |
205 ms |
22436 KB |
Output is correct |
| 6 |
Correct |
469 ms |
41996 KB |
Output is correct |
| 7 |
Correct |
168 ms |
22508 KB |
Output is correct |
| 8 |
Correct |
531 ms |
45308 KB |
Output is correct |
| 9 |
Correct |
356 ms |
45740 KB |
Output is correct |
| 10 |
Correct |
520 ms |
45344 KB |
Output is correct |
| 11 |
Correct |
350 ms |
45808 KB |
Output is correct |
| 12 |
Correct |
159 ms |
20172 KB |
Output is correct |
| 13 |
Correct |
232 ms |
35568 KB |
Output is correct |
| 14 |
Correct |
343 ms |
42496 KB |
Output is correct |
| 15 |
Correct |
350 ms |
42276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
316 KB |
Output is correct |
| 2 |
Correct |
0 ms |
308 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
