| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 645731 |
2022-09-27T18:41:49 Z |
rainboy |
Fish 2 (JOI22_fish2) |
C |
|
1 ms |
212 KB |
#include <stdio.h>
#include <string.h>
#define N 100000
#define N_ (1 << 17) /* N_ = pow2(ceil(log2(N + 1))) */
#define INF 0x7fffffff
#define LG 30
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int aa[N], st1[N_ * 2], st2[N_ * 2], kk2[N_ * 2], lz2[N_], h_, n_;
void pul1(int i) {
st1[i] = st1[i << 1 | 0] <= INF - st1[i << 1 | 1] ? st1[i << 1 | 0] + st1[i << 1 | 1] : INF;
}
void build(int *aa, int n) {
int i;
h_ = 0;
while (1 << h_ <= n)
h_++;
n_ = 1 << h_;
for (i = 0; i < n; i++)
st1[n_ + i] = aa[i], kk2[n_ + i] = 1;
for (i = n_ - 1; i > 0; i--)
pul1(i);
}
void update1(int i, int a) {
i += n_;
st1[i] = a;
while (i > 1)
pul1(i >>= 1);
}
int queryl1(int r, int s) {
int l = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
if ((r & 1) == 0) {
if (s > st1[r])
s -= st1[r--];
else {
while (r < n_)
if (s <= st1[r << 1 | 1])
r = r << 1 | 1;
else
s -= st1[r << 1 | 1], r = r << 1 | 0;
return r - n_;
}
}
return -1;
}
int queryr1(int l, int s) {
int r = n_ - 1;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
if ((l & 1) == 1) {
if (s > st1[l])
s -= st1[l++];
else {
while (l < n_)
if (s <= st1[l << 1 | 0])
l = l << 1 | 0;
else
s -= st1[l << 1 | 0], l = l << 1 | 1;
return l - n_;
}
}
return n_;
}
void put2(int i, int x) {
st2[i] += x;
if (i < n_)
lz2[i] += x;
}
void pus2(int i) {
if (lz2[i])
put2(i << 1 | 0, lz2[i]), put2(i << 1 | 1, lz2[i]), lz2[i] = 0;
}
void pul2(int i) {
if (!lz2[i]) {
int l = i << 1, r = l | 1;
if (st2[l] < st2[r])
st2[i] = st2[l], kk2[i] = kk2[l];
else if (st2[l] > st2[r])
st2[i] = st2[r], kk2[i] = kk2[r];
else
st2[i] = st2[l], kk2[i] = kk2[l] + kk2[r];
}
}
void push2(int i) {
int h;
for (h = h_; h > 0; h--)
pus2(i >> h);
}
void pull2(int i) {
while (i > 1)
pul2(i >>= 1);
}
void update2(int l, int r, int x) {
int l_ = l += n_, r_ = r += n_;
if (l > r)
return;
push2(l_), push2(r_);
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
put2(l++, x);
if ((r & 1) == 0)
put2(r--, x);
}
pull2(l_), pull2(r_);
}
int query2(int l, int r) {
int x = INF, k = 0;
if (l > r)
return 0;
push2(l += n_), push2(r += n_);
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1) {
if (x > st2[l])
x = st2[l], k = 0;
if (x == st2[l])
k += kk2[l];
l++;
}
if ((r & 1) == 0) {
if (x > st2[r])
x = st2[r], k = 0;
if (x == st2[r])
k += kk2[r];
r--;
}
}
return x == 0 ? k : 0;
}
int ll[N], rr[N];
void updl(int l, int i, int x) {
if (ll[i] < l || aa[ll[i]] > aa[i])
update2(ll[i] + 1, i - 1, x);
}
void updr(int r, int i, int x) {
if (rr[i] > r || aa[rr[i]] >= aa[i])
update2(i + 1, rr[i] - 1, x);
}
void upd(int l, int r, int i, int x) {
updl(l, i, x), updr(r, i, x);
}
int main() {
int n, q, i, j;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &aa[i]);
build(aa, n);
scanf("%d", &q);
for (i = 0; i < n; i++) {
ll[i] = queryl1(i - 1, aa[i]), rr[i] = queryr1(i + 1, aa[i]);
updl(0, i, 1), updr(n - 1, i, 1);
}
while (q--) {
static char used[N];
static int qu[N];
int t, a, l, r, lg, cnt, h;
scanf("%d", &t);
if (t == 1) {
scanf("%d%d", &i, &a), i--;
cnt = 0;
qu[cnt++] = i;
for (lg = 0; lg <= LG; lg++) {
j = queryl1(i - 1, 1 << lg);
if (j >= 0 && !used[j])
used[j] = 1, qu[cnt++] = j;
j = queryr1(i + 1, 1 << lg);
if (j < n && !used[j])
used[j] = 1, qu[cnt++] = j;
}
for (h = 0; h < cnt; h++) {
if (qu[h] <= i)
updr(n - 1, qu[h], -1);
if (qu[h] >= i)
updl(0, qu[h], -1);
}
aa[i] = a, update1(i, a);
for (h = 0; h < cnt; h++) {
if (qu[h] <= i) {
rr[qu[h]] = queryr1(qu[h] + 1, aa[qu[h]]);
updr(n - 1, qu[h], 1);
}
if (qu[h] >= i) {
ll[qu[h]] = queryl1(qu[h] - 1, aa[qu[h]]);
updl(0, qu[h], 1);
}
used[qu[h]] = 0;
}
} else {
scanf("%d%d", &l, &r), l--, r--;
cnt = 0;
for (lg = 0; lg <= LG; lg++) {
j = queryl1(l - 1, 1 << lg);
if (j >= 0 && !used[j])
used[j] = 1, qu[cnt++] = j;
j = queryr1(l, 1 << lg);
if (j < n && !used[j])
used[j] = 1, qu[cnt++] = j;
j = queryl1(r, 1 << lg);
if (j >= 0 && !used[j])
used[j] = 1, qu[cnt++] = j;
j = queryr1(r + 1, 1 << lg);
if (j < n && !used[j])
used[j] = 1, qu[cnt++] = j;
}
for (h = 0; h < cnt; h++) {
upd(0, n - 1, qu[h], -1);
if (l <= qu[h] && qu[h] <= r)
upd(l, r, qu[h], 1);
}
printf("%d\n", query2(l, r));
for (h = 0; h < cnt; h++) {
if (l <= qu[h] && qu[h] <= r)
upd(l, r, qu[h], -1);
upd(0, n - 1, qu[h], 1);
}
for (h = 0; h < cnt; h++)
used[qu[h]] = 0;
}
}
return 0;
}
Compilation message
fish2.c: In function 'main':
fish2.c:171:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
171 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
fish2.c:173:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
173 | scanf("%d", &aa[i]);
| ^~~~~~~~~~~~~~~~~~~
fish2.c:175:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
175 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
fish2.c:185:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
185 | scanf("%d", &t);
| ^~~~~~~~~~~~~~~
fish2.c:187:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
187 | scanf("%d%d", &i, &a), i--;
| ^~~~~~~~~~~~~~~~~~~~~
fish2.c:217:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
217 | scanf("%d%d", &l, &r), l--, r--;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
