| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 704748 |
2023-03-02T22:24:54 Z |
rainboy |
None (JOI16_ho_t5) |
C |
|
877 ms |
30464 KB |
#include <stdio.h>
#define N 200000
#define N_ (1 << 18) /* N_ = pow2(ceil(log2(N))) */
#define Q 200000
long long uumn[N_ * 2], uumx[N_ * 2], vvmn[N_ * 2], vvmx[N_ * 2], ulz[N_], vlz[N_]; int h_, n_;
void put(int i, long long u, long long v) {
uumn[i] += u, uumx[i] += u;
vvmn[i] += v, vvmx[i] += v;
if (i < n_)
ulz[i] += u, vlz[i] += v;
}
void pus(int i) {
if (ulz[i] || vlz[i])
put(i << 1 | 0, ulz[i], vlz[i]), put(i << 1 | 1, ulz[i], vlz[i]), ulz[i] = vlz[i] = 0;
}
void pul(int i) {
if (!ulz[i] && !vlz[i]) {
int l = i << 1, r = l | 1;
uumn[i] = uumn[l], uumx[i] = uumx[r];
vvmn[i] = vvmn[l], vvmx[i] = vvmx[r];
}
}
void build(int n) {
int i;
h_ = 0;
while (1 << h_ < n)
h_++;
n_ = 1 << h_;
for (i = 0; i < n_; i++)
uumn[n_ + i] = i, uumx[n_ + i] = i, vvmn[n_ + i] = i, vvmx[n_ + i] = i;
for (i = n_ - 1; i > 0; i--)
pul(i);
}
void push(int i) {
int h;
for (h = h_; h > 0; h--)
pus(i >> h);
}
void pull(int i) {
while (i > 1)
pul(i >>= 1);
}
void update(int l, int r, long long u, long long v) {
int l_, r_;
if (l > r)
return;
l_ = l += n_, r_ = r += n_;
push(l_), push(r_);
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
put(l++, u, v);
if ((r & 1) == 0)
put(r--, u, v);
}
pull(l_), pull(r_);
}
int query_u(int u) {
int i = 1;
while (i < n_) {
pus(i);
if (uumx[i << 1 | 0] < u)
i = i << 1 | 1;
else
i = i << 1 | 0;
}
return (uumx[i] < u ? i : i - 1) - n_;
}
int query_v(int v) {
int i = 1;
while (i < n_) {
pus(i);
if (vvmn[i << 1 | 1] >= v)
i = i << 1 | 0;
else
i = i << 1 | 1;
}
return (vvmn[i] >= v ? i : i + 1) - n_;
}
int main() {
static int tt[Q], xx[Q], vv[Q];
int n, q, h, i;
scanf("%d%d", &n, &q);
for (h = 0; h < q; h++)
scanf("%d%d%d", &xx[h], &tt[h], &vv[h]);
build(n);
for (h = q - 1; h >= 0; h--)
if (tt[h] == 1)
update(0, query_u(xx[h]), 0, -vv[h] * 2);
else
update(query_v(xx[h]), n_ - 1, vv[h] * 2, 0);
for (i = 0; i < n_; i++)
pus(i);
for (i = 0; i < n; i++)
printf("%lld\n", (uumn[n_ + i] - vvmn[n_ + i]) / 2);
return 0;
}
Compilation message
2016_ho_t5.c: In function 'main':
2016_ho_t5.c:101:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%d%d", &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~
2016_ho_t5.c:103:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d%d%d", &xx[h], &tt[h], &vv[h]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 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 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
296 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
296 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
0 ms |
288 KB |
Output is correct |
| 22 |
Correct |
0 ms |
340 KB |
Output is correct |
| 23 |
Correct |
0 ms |
340 KB |
Output is correct |
| 24 |
Correct |
0 ms |
340 KB |
Output is correct |
| 25 |
Correct |
0 ms |
340 KB |
Output is correct |
| 26 |
Correct |
0 ms |
340 KB |
Output is correct |
| 27 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 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 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
296 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
296 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
0 ms |
288 KB |
Output is correct |
| 22 |
Correct |
0 ms |
340 KB |
Output is correct |
| 23 |
Correct |
0 ms |
340 KB |
Output is correct |
| 24 |
Correct |
0 ms |
340 KB |
Output is correct |
| 25 |
Correct |
0 ms |
340 KB |
Output is correct |
| 26 |
Correct |
0 ms |
340 KB |
Output is correct |
| 27 |
Correct |
0 ms |
340 KB |
Output is correct |
| 28 |
Correct |
4 ms |
724 KB |
Output is correct |
| 29 |
Correct |
4 ms |
732 KB |
Output is correct |
| 30 |
Correct |
4 ms |
724 KB |
Output is correct |
| 31 |
Correct |
4 ms |
724 KB |
Output is correct |
| 32 |
Correct |
4 ms |
724 KB |
Output is correct |
| 33 |
Correct |
4 ms |
724 KB |
Output is correct |
| 34 |
Correct |
5 ms |
684 KB |
Output is correct |
| 35 |
Correct |
5 ms |
724 KB |
Output is correct |
| 36 |
Correct |
4 ms |
724 KB |
Output is correct |
| 37 |
Correct |
4 ms |
728 KB |
Output is correct |
| 38 |
Correct |
4 ms |
724 KB |
Output is correct |
| 39 |
Correct |
3 ms |
724 KB |
Output is correct |
| 40 |
Correct |
4 ms |
724 KB |
Output is correct |
| 41 |
Correct |
4 ms |
752 KB |
Output is correct |
| 42 |
Correct |
4 ms |
724 KB |
Output is correct |
| 43 |
Correct |
2 ms |
724 KB |
Output is correct |
| 44 |
Correct |
3 ms |
724 KB |
Output is correct |
| 45 |
Correct |
3 ms |
724 KB |
Output is correct |
| 46 |
Correct |
4 ms |
724 KB |
Output is correct |
| 47 |
Correct |
4 ms |
724 KB |
Output is correct |
| 48 |
Correct |
5 ms |
728 KB |
Output is correct |
| 49 |
Correct |
4 ms |
724 KB |
Output is correct |
| 50 |
Correct |
5 ms |
724 KB |
Output is correct |
| 51 |
Correct |
5 ms |
728 KB |
Output is correct |
| 52 |
Correct |
4 ms |
688 KB |
Output is correct |
| 53 |
Correct |
6 ms |
724 KB |
Output is correct |
| 54 |
Correct |
5 ms |
724 KB |
Output is correct |
| 55 |
Correct |
5 ms |
684 KB |
Output is correct |
| 56 |
Correct |
4 ms |
724 KB |
Output is correct |
| 57 |
Correct |
5 ms |
724 KB |
Output is correct |
| 58 |
Correct |
5 ms |
716 KB |
Output is correct |
| 59 |
Correct |
5 ms |
724 KB |
Output is correct |
| 60 |
Correct |
4 ms |
724 KB |
Output is correct |
| 61 |
Correct |
5 ms |
684 KB |
Output is correct |
| 62 |
Correct |
5 ms |
688 KB |
Output is correct |
| 63 |
Correct |
5 ms |
724 KB |
Output is correct |
| 64 |
Correct |
5 ms |
724 KB |
Output is correct |
| 65 |
Correct |
5 ms |
724 KB |
Output is correct |
| 66 |
Correct |
5 ms |
684 KB |
Output is correct |
| 67 |
Correct |
5 ms |
692 KB |
Output is correct |
| 68 |
Correct |
5 ms |
692 KB |
Output is correct |
| 69 |
Correct |
6 ms |
688 KB |
Output is correct |
| 70 |
Correct |
1 ms |
596 KB |
Output is correct |
| 71 |
Correct |
1 ms |
596 KB |
Output is correct |
| 72 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 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 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
296 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
296 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
0 ms |
288 KB |
Output is correct |
| 22 |
Correct |
0 ms |
340 KB |
Output is correct |
| 23 |
Correct |
0 ms |
340 KB |
Output is correct |
| 24 |
Correct |
0 ms |
340 KB |
Output is correct |
| 25 |
Correct |
0 ms |
340 KB |
Output is correct |
| 26 |
Correct |
0 ms |
340 KB |
Output is correct |
| 27 |
Correct |
0 ms |
340 KB |
Output is correct |
| 28 |
Correct |
4 ms |
724 KB |
Output is correct |
| 29 |
Correct |
4 ms |
732 KB |
Output is correct |
| 30 |
Correct |
4 ms |
724 KB |
Output is correct |
| 31 |
Correct |
4 ms |
724 KB |
Output is correct |
| 32 |
Correct |
4 ms |
724 KB |
Output is correct |
| 33 |
Correct |
4 ms |
724 KB |
Output is correct |
| 34 |
Correct |
5 ms |
684 KB |
Output is correct |
| 35 |
Correct |
5 ms |
724 KB |
Output is correct |
| 36 |
Correct |
4 ms |
724 KB |
Output is correct |
| 37 |
Correct |
4 ms |
728 KB |
Output is correct |
| 38 |
Correct |
4 ms |
724 KB |
Output is correct |
| 39 |
Correct |
3 ms |
724 KB |
Output is correct |
| 40 |
Correct |
4 ms |
724 KB |
Output is correct |
| 41 |
Correct |
4 ms |
752 KB |
Output is correct |
| 42 |
Correct |
4 ms |
724 KB |
Output is correct |
| 43 |
Correct |
2 ms |
724 KB |
Output is correct |
| 44 |
Correct |
3 ms |
724 KB |
Output is correct |
| 45 |
Correct |
3 ms |
724 KB |
Output is correct |
| 46 |
Correct |
4 ms |
724 KB |
Output is correct |
| 47 |
Correct |
4 ms |
724 KB |
Output is correct |
| 48 |
Correct |
5 ms |
728 KB |
Output is correct |
| 49 |
Correct |
4 ms |
724 KB |
Output is correct |
| 50 |
Correct |
5 ms |
724 KB |
Output is correct |
| 51 |
Correct |
5 ms |
728 KB |
Output is correct |
| 52 |
Correct |
4 ms |
688 KB |
Output is correct |
| 53 |
Correct |
6 ms |
724 KB |
Output is correct |
| 54 |
Correct |
5 ms |
724 KB |
Output is correct |
| 55 |
Correct |
5 ms |
684 KB |
Output is correct |
| 56 |
Correct |
4 ms |
724 KB |
Output is correct |
| 57 |
Correct |
5 ms |
724 KB |
Output is correct |
| 58 |
Correct |
5 ms |
716 KB |
Output is correct |
| 59 |
Correct |
5 ms |
724 KB |
Output is correct |
| 60 |
Correct |
4 ms |
724 KB |
Output is correct |
| 61 |
Correct |
5 ms |
684 KB |
Output is correct |
| 62 |
Correct |
5 ms |
688 KB |
Output is correct |
| 63 |
Correct |
5 ms |
724 KB |
Output is correct |
| 64 |
Correct |
5 ms |
724 KB |
Output is correct |
| 65 |
Correct |
5 ms |
724 KB |
Output is correct |
| 66 |
Correct |
5 ms |
684 KB |
Output is correct |
| 67 |
Correct |
5 ms |
692 KB |
Output is correct |
| 68 |
Correct |
5 ms |
692 KB |
Output is correct |
| 69 |
Correct |
6 ms |
688 KB |
Output is correct |
| 70 |
Correct |
1 ms |
596 KB |
Output is correct |
| 71 |
Correct |
1 ms |
596 KB |
Output is correct |
| 72 |
Correct |
1 ms |
596 KB |
Output is correct |
| 73 |
Correct |
721 ms |
26404 KB |
Output is correct |
| 74 |
Correct |
730 ms |
26592 KB |
Output is correct |
| 75 |
Correct |
694 ms |
26752 KB |
Output is correct |
| 76 |
Correct |
680 ms |
26656 KB |
Output is correct |
| 77 |
Correct |
655 ms |
26612 KB |
Output is correct |
| 78 |
Correct |
613 ms |
26700 KB |
Output is correct |
| 79 |
Correct |
575 ms |
26756 KB |
Output is correct |
| 80 |
Correct |
421 ms |
27028 KB |
Output is correct |
| 81 |
Correct |
516 ms |
27420 KB |
Output is correct |
| 82 |
Correct |
538 ms |
27304 KB |
Output is correct |
| 83 |
Correct |
668 ms |
28028 KB |
Output is correct |
| 84 |
Correct |
609 ms |
27976 KB |
Output is correct |
| 85 |
Correct |
622 ms |
28212 KB |
Output is correct |
| 86 |
Correct |
334 ms |
28620 KB |
Output is correct |
| 87 |
Correct |
274 ms |
29240 KB |
Output is correct |
| 88 |
Correct |
460 ms |
30448 KB |
Output is correct |
| 89 |
Correct |
398 ms |
30464 KB |
Output is correct |
| 90 |
Correct |
675 ms |
28920 KB |
Output is correct |
| 91 |
Correct |
681 ms |
25476 KB |
Output is correct |
| 92 |
Correct |
678 ms |
25756 KB |
Output is correct |
| 93 |
Correct |
729 ms |
28192 KB |
Output is correct |
| 94 |
Correct |
725 ms |
25572 KB |
Output is correct |
| 95 |
Correct |
796 ms |
28524 KB |
Output is correct |
| 96 |
Correct |
830 ms |
26400 KB |
Output is correct |
| 97 |
Correct |
783 ms |
27480 KB |
Output is correct |
| 98 |
Correct |
877 ms |
26292 KB |
Output is correct |
| 99 |
Correct |
797 ms |
28360 KB |
Output is correct |
| 100 |
Correct |
787 ms |
26268 KB |
Output is correct |
| 101 |
Correct |
753 ms |
27768 KB |
Output is correct |
| 102 |
Correct |
820 ms |
26484 KB |
Output is correct |
| 103 |
Correct |
810 ms |
28460 KB |
Output is correct |
| 104 |
Correct |
745 ms |
26340 KB |
Output is correct |
| 105 |
Correct |
712 ms |
27976 KB |
Output is correct |
| 106 |
Correct |
832 ms |
26464 KB |
Output is correct |
| 107 |
Correct |
771 ms |
28224 KB |
Output is correct |
| 108 |
Correct |
809 ms |
26328 KB |
Output is correct |
| 109 |
Correct |
793 ms |
27784 KB |
Output is correct |
| 110 |
Correct |
822 ms |
26700 KB |
Output is correct |
| 111 |
Correct |
842 ms |
29392 KB |
Output is correct |
| 112 |
Correct |
732 ms |
26584 KB |
Output is correct |
| 113 |
Correct |
807 ms |
29772 KB |
Output is correct |
| 114 |
Correct |
739 ms |
26572 KB |
Output is correct |
| 115 |
Correct |
747 ms |
26956 KB |
Output is correct |
| 116 |
Correct |
742 ms |
26692 KB |
Output is correct |
| 117 |
Correct |
752 ms |
29808 KB |
Output is correct |
| 118 |
Correct |
744 ms |
26580 KB |
Output is correct |
| 119 |
Correct |
28 ms |
22988 KB |
Output is correct |
| 120 |
Correct |
21 ms |
17020 KB |
Output is correct |
