| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 708514 |
2023-03-11T23:37:29 Z |
rainboy |
Dungeon 3 (JOI21_ho_t5) |
C |
|
1000 ms |
39936 KB |
/* https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t5-review.pdf */
#include <stdio.h>
#define N 200000
#define N_ (1 << 18) /* N_ = pow2(ceil(log2(N))) */
#define N4 (N * 4 + 1)
#define M 200000
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int dd[N], cc[N], kk[N], n; long long xx[N + 1];
int ll[M], ll1[M * 2], rr[M], tt[M], m; long long ans[M];
int st[N_ * 2], n_;
void build(int *aa, int n) {
int i;
n_ = 1;
while (n_ < n)
n_ <<= 1;
for (i = 0; i < n; i++)
st[n_ + i] = aa[i];
for (i = n_ - 1; i > 0; i--)
st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}
int st_query(int l, int r) {
int x;
x = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
x = max(x, st[l++]);
if ((r & 1) == 0)
x = max(x, st[r--]);
}
return x;
}
int *vv;
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k)
if (vv[hh[j]] == vv[h])
j++;
else if (vv[hh[j]] < vv[h]) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
sort(hh, l, i);
l = k;
}
}
int zz[N4], ll_[N4], rr_[N4], u_, l_, r_; long long xx_[N4], aa[N4], aa_[N4], bb[N4], bb_[N4];
int node(long long x, long long a, long long b) {
static int _ = 1;
zz[_] = rand_();
xx_[_] = x, aa_[_] = aa[_] = a, bb_[_] = bb[_] = b;
return _++;
}
void pul(int u) {
int l = ll_[u], r = rr_[u];
aa_[u] = aa_[l] + aa[u] + aa_[r], bb_[u] = bb_[l] + bb[u] + bb_[r];
}
void split(int u, long long x) {
if (u == 0) {
u_ = u, l_ = r_ = 0;
return;
}
if (xx_[u] < x) {
split(rr_[u], x);
rr_[u] = l_, l_ = u;
} else if (xx_[u] > x) {
split(ll_[u], x);
ll_[u] = r_, r_ = u;
} else {
u_ = u, l_ = ll_[u], r_ = rr_[u];
ll_[u] = rr_[u] = 0;
}
pul(u);
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr_[u] = merge(rr_[u], v), pul(u);
return u;
} else {
ll_[v] = merge(u, ll_[v]), pul(v);
return v;
}
}
void tr_update(long long x, long long a, long long b) {
split(u_, x);
if (u_ == 0)
u_ = node(x, a, b);
else
aa_[u_] = aa[u_] += a, bb_[u_] = bb[u_] += b;
u_ = merge(merge(l_, u_), r_);
}
long long tr_query(long long x) {
int u;
long long a, b;
u = u_, a = 0, b = 0;
while (u)
if (xx_[u] <= x)
a += aa_[u] - aa_[rr_[u]], b += bb_[u] - bb_[rr_[u]], u = rr_[u];
else
u = ll_[u];
return a * x + b;
}
int main() {
static int qu[N], hh[M], hh_[M * 2];
int m_, cnt, g, h, h_, i, j, lower, upper;
scanf("%d%d", &n, &m);
xx[0] = 0;
for (i = 0; i < n; i++) {
scanf("%d", &dd[i]);
xx[i + 1] = xx[i] + dd[i];
}
build(dd, n);
for (i = 0; i < n; i++)
scanf("%d", &cc[i]);
for (h = 0; h < m; h++)
scanf("%d%d%d", &ll[h], &rr[h], &tt[h]), ll[h]--, rr[h]--;
for (h = 0; h < m; h++)
hh[h] = h;
vv = rr, sort(hh, 0, m);
cnt = 0, m_ = 0;
for (h = 0, i = 0; i <= n; i++) {
while (h < m && rr[h_ = hh[h]] == i) {
if (tt[h_] < st_query(ll[h_], rr[h_] - 1))
ans[h_] = -1;
else {
lower = -1, upper = cnt - 1;
while (upper - lower > 1) {
g = (lower + upper) / 2;
if (xx[i] - xx[qu[g]] <= tt[h_])
upper = g;
else
lower = g;
}
g = upper;
ans[h_] += (xx[i] - xx[qu[g]]) * cc[qu[g]];
ll1[h_ << 1 | 0] = ll[h_], hh_[m_++] = h_ << 1 | 0;
ll1[h_ << 1 | 1] = qu[g], hh_[m_++] = h_ << 1 | 1;
}
h++;
}
if (i < n) {
while (cnt && cc[qu[cnt - 1]] > cc[i])
cnt--;
qu[cnt++] = i;
}
}
vv = ll1, sort(hh_, 0, m_);
cnt = 0;
for (i = n, h = m_ - 1; i >= 0; i--) {
if (i < n) {
while (cnt && cc[j = qu[cnt - 1]] >= cc[i]) {
tr_update(xx[j] - xx[i], -cc[j], (xx[j] - xx[i]) * cc[j]);
tr_update(xx[kk[j]] - xx[i], cc[j], -(xx[kk[j]] - xx[i]) * cc[j]);
cnt--;
}
kk[i] = cnt == 0 ? n : qu[cnt - 1];
tr_update(0, cc[i], 0);
tr_update(xx[kk[i]] - xx[i], -cc[i], (xx[kk[i]] - xx[i]) * cc[i]);
qu[cnt++] = i;
}
while (h >= 0 && ll1[h_ = hh_[h]] == i) {
ans[h_ >> 1] += tr_query(tt[h_ >> 1]) * ((h_ & 1) == 0 ? 1 : -1);
h--;
}
}
for (h = 0; h < m; h++)
printf("%lld\n", ans[h]);
return 0;
}
Compilation message
Main.c: In function 'main':
Main.c:142:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
Main.c:145:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
145 | scanf("%d", &dd[i]);
| ^~~~~~~~~~~~~~~~~~~
Main.c:150:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | scanf("%d", &cc[i]);
| ^~~~~~~~~~~~~~~~~~~
Main.c:152:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | scanf("%d%d%d", &ll[h], &rr[h], &tt[h]), ll[h]--, rr[h]--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
9424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1000 ms |
24516 KB |
Output is correct |
| 2 |
Correct |
636 ms |
36336 KB |
Output is correct |
| 3 |
Correct |
482 ms |
30540 KB |
Output is correct |
| 4 |
Correct |
763 ms |
37156 KB |
Output is correct |
| 5 |
Correct |
418 ms |
39936 KB |
Output is correct |
| 6 |
Correct |
618 ms |
35644 KB |
Output is correct |
| 7 |
Correct |
473 ms |
23244 KB |
Output is correct |
| 8 |
Correct |
445 ms |
32456 KB |
Output is correct |
| 9 |
Correct |
263 ms |
22920 KB |
Output is correct |
| 10 |
Correct |
369 ms |
33468 KB |
Output is correct |
| 11 |
Correct |
627 ms |
39800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
