#include <stdio.h>
#define N 500000
#define N_ (1 << 19) /* N_ = pow2(ceil(log2(N + 1))) */
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int tt[N], xx[N], yy[N], n, n_; long long kk[N];
int *ww, mode;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = ww[ii[j]] != ww[i_] ? ww[ii[j]] - ww[i_] : (mode == 0 ? tt[ii[j]] - tt[i_] : tt[i_] - tt[ii[j]]);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
long long st1[N_ * 2];
void pul1(int i) {
st1[i] = st1[i << 1 | 0] + st1[i << 1 | 1];
}
void update1(int i, long long x) {
i += n_;
st1[i] += x;
while (i > 1)
pul1(i >>= 1);
}
int query1(int l) {
int r = n_ - 1, i;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
if ((l & 1) == 1) {
if (st1[l]) {
i = l;
while (i < n_)
i = st1[i << 1 | 0] ? i << 1 | 0 : i << 1 | 1;
return i - n_;
}
l++;
}
return -1;
}
long long st2[N_ * 2];
void pul2(int i) {
st2[i] = st2[i << 1 | 0] + st2[i << 1 | 1];
}
void update2(int i, long long x) {
i += n_;
st2[i] += x;
while (i > 1)
pul2(i >>= 1);
}
int query2(int r) {
int l = 0, i;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
if ((r & 1) == 0) {
if (st2[r]) {
i = r;
while (i < n_)
i = st2[i << 1 | 1] ? i << 1 | 1 : i << 1 | 0;
return i - n_;
}
r--;
}
return -1;
}
long long sum12[N_ * 2], pref12[N_ * 2], suf12[N_ * 2];
void pul12(int i) {
int l = i << 1, r = l | 1;
sum12[i] = sum12[l] + sum12[r];
pref12[i] = min(pref12[l], sum12[l] + pref12[r]);
suf12[i] = max(suf12[r], sum12[r] + suf12[l]);
}
void update12(int i, long long x) {
i += n_;
sum12[i] += x, pref12[i] = min(sum12[i], 0), suf12[i] = max(sum12[i], 0);
while (i > 1)
pul12(i >>= 1);
}
int query12l(int l) {
int r = n_ - 1, i;
long long s, p;
s = 0, p = 0, i = -1;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
if ((l & 1) == 1) {
if (p > s + pref12[l])
p = s + pref12[l], i = l;
s += sum12[l];
l++;
}
if (i == -1)
return -1;
while (i < n_)
i = pref12[i << 1 | 0] < sum12[i << 1 | 0] + pref12[i << 1 | 1] ? i << 1 | 0 : i << 1 | 1;
return i - n_;
}
int query12r(int r) {
int l = 0, i;
long long s, q;
s = 0, q = 0, i = -1;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
if ((r & 1) == 0) {
if (q < s + suf12[r])
q = s + suf12[r], i = r;
s += sum12[r];
r--;
}
if (i == -1)
return -1;
while (i < n_)
i = suf12[i << 1 | 1] > sum12[i << 1 | 1] + suf12[i << 1 | 0] ? i << 1 | 1 : i << 1 | 0;
return i - n_;
}
long long query12p(int l, int r) {
long long sl = 0, pl = 0, pr = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
pl = min(pl, sl + pref12[l]), sl += sum12[l], l++;
if ((r & 1) == 0)
pr = min(pref12[r], sum12[r] + pr), r--;
}
return min(pl, sl + pr);
}
long long query12q(int l, int r) {
long long sr = 0, ql = 0, qr = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
ql = max(sum12[l] + ql, suf12[l]), l++;
if ((r & 1) == 0)
qr = max(qr, sr + suf12[r]), sr += sum12[r], r--;
}
return max(qr, sr + ql);
}
long long sum21[N_ * 2], pref21[N_ * 2];
void pul21(int i) {
int l = i << 1, r = l | 1;
sum21[i] = sum21[l] + sum21[r];
pref21[i] = min(pref21[l], sum21[l] + pref21[r]);
}
void update21(int i, long long x) {
i += n_;
sum21[i] += x, pref21[i] = min(sum21[i], 0);
while (i > 1)
pul21(i >>= 1);
}
long long query21s(int l, int r) {
long long sum = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
sum += sum21[l++];
if ((r & 1) == 0)
sum += sum21[r--];
}
return sum;
}
long long query21p(int l, int r) {
long long s = query21s(0, l - 1), sl = 0, pl = 0, pr = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
pl = min(pl, sl + pref21[l]), sl += sum21[l], l++;
if ((r & 1) == 0)
pr = min(pref21[r], sum21[r] + pr), r--;
}
return s + min(pl, sl + pr);
}
int main() {
static int ii[N], jj[N];
int d, i, i_, j;
long long ans, k;
scanf("%d%d", &n, &d);
for (i = 0; i < n; i++) {
int x;
scanf("%d%d%lld", &tt[i], &x, &kk[i]);
if (tt[i] == 1)
xx[i] = x, yy[i] = x + d;
else
xx[i] = x + d, yy[i] = x;
}
for (i = 0; i < n; i++)
ii[i] = i;
ww = xx, mode = 0, sort(ii, 0, n);
for (i = 0; i < n; i++)
xx[ii[i]] = i;
for (j = 0; j < n; j++)
jj[j] = j;
ww = yy, mode = 1, sort(jj, 0, n);
for (j = 0; j < n; j++)
yy[jj[j]] = j;
n_ = 1;
while (n_ <= n)
n_ <<= 1;
ans = 0;
for (i = 0; i < n; i++) {
if (tt[i] == 1) {
update2(xx[i], kk[i]);
while (1) {
j = query1(xx[i] + 1);
if (j == -1)
break;
j = ii[j];
k = min(kk[i], kk[j]);
if (yy[i] < yy[j])
k = min(k, query21p(yy[i], yy[j] - 1));
if (k == 0)
break;
kk[i] -= k, kk[j] -= k;
update1(xx[j], -k);
update2(xx[i], -k);
update12(xx[i], k), update12(xx[j], -k);
update21(yy[j], k), update21(yy[i], -k);
ans += k;
}
while (1) {
i_ = query12r(xx[i] - 1);
if (i_ == -1)
break;
i_ = ii[i_];
k = min(kk[i], query12q(xx[i_], xx[i] - 1) - query12q(xx[i_] + 1, xx[i] - 1));
if (k == 0)
break;
if (i == i_)
return 0;
kk[i] -= k, kk[i_] += k;
update2(xx[i_], k), update2(xx[i], -k);
update12(xx[i_], -k), update12(xx[i], k);
update21(yy[i_], k), update21(yy[i], -k);
}
} else {
update1(xx[i], kk[i]);
while (1) {
j = query2(xx[i] - 1);
if (j == -1)
break;
j = ii[j];
k = min(kk[i], kk[j]);
if (yy[i] > yy[j])
k = min(k, query21p(yy[j], yy[i] - 1));
if (k == 0)
break;
kk[i] -= k, kk[j] -= k;
update1(xx[i], -k);
update2(xx[j], -k);
update12(xx[j], k), update12(xx[i], -k);
update21(yy[i], k), update21(yy[j], -k);
ans += k;
}
while (1) {
i_ = query12l(xx[i] + 1);
if (i_ == -1)
break;
i_ = ii[i_];
k = min(kk[i], query12p(xx[i] + 1, xx[i_] - 1) - query12p(xx[i] + 1, xx[i_]));
if (k == 0)
break;
kk[i] -= k, kk[i_] += k;
update1(xx[i_], k), update1(xx[i], -k);
update12(xx[i_], k), update12(xx[i], -k);
update21(yy[i_], -k), update21(yy[i], k);
}
}
printf("%lld\n", ans);
}
return 0;
}
Compilation message
sugar.c: In function 'main':
sugar.c:223:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
223 | scanf("%d%d", &n, &d);
| ^~~~~~~~~~~~~~~~~~~~~
sugar.c:227:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
227 | scanf("%d%d%lld", &tt[i], &x, &kk[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
288 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
684 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
292 KB |
Output is correct |
| 2 |
Correct |
0 ms |
288 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
855 ms |
62140 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
341 ms |
33596 KB |
Output is correct |
| 3 |
Correct |
470 ms |
45772 KB |
Output is correct |
| 4 |
Runtime error |
343 ms |
50836 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
288 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
684 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
