| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 832487 |
2023-08-21T10:51:15 Z |
rainboy |
ZIGZAG (INOI20_zigzag) |
C |
|
344 ms |
28456 KB |
#include <stdio.h>
#define N 300000
#define N_ (1 << 19) /* N_ = pow2(ceil(log2(N))) */
int sgn(long long a) { return a == 0 ? 0 : (a < 0 ? -1 : 1); }
int h_, n_;
int aa_[N_ * 2]; long long bb_[N_ * 2];
void put(int i, int a, long long b) {
aa_[i] *= a, bb_[i] = bb_[i] * a + b;
}
void pus(int i) {
if (aa_[i] != 1 || bb_[i] != 0)
put(i << 1 | 0, aa_[i], bb_[i]), put(i << 1 | 1, aa_[i], bb_[i]), aa_[i] = 1, bb_[i] = 0;
}
void push(int i) {
int h;
for (h = h_; h > 0; h--)
pus(i >> h);
}
int sz[N_ * 2], pppos[N_ * 2], ppneg[N_ * 2], qqpos[N_ * 2], qqneg[N_ * 2]; long long st[N_ * 2]; char lz[N_];
void put_(int i) {
int tmp;
tmp = pppos[i], pppos[i] = ppneg[i], ppneg[i] = tmp;
tmp = qqpos[i], qqpos[i] = qqneg[i], qqneg[i] = tmp;
if (i < n_)
lz[i] ^= 1;
}
void pus_(int i) {
if (lz[i])
put_(i << 1 | 0), put_(i << 1 | 1), lz[i] = 0;
}
void pul_(int i) {
if (!lz[i]) {
int l = i << 1, r = l | 1;
pppos[i] = pppos[l] < sz[l] ? pppos[l] : sz[l] + pppos[r];
ppneg[i] = ppneg[l] < sz[l] ? ppneg[l] : sz[l] + ppneg[r];
qqpos[i] = qqpos[r] < sz[r] ? qqpos[r] : qqpos[l] + sz[r];
qqneg[i] = qqneg[r] < sz[r] ? qqneg[r] : qqneg[l] + sz[r];
st[i] = st[l] + st[r] + (long long) qqpos[l] * pppos[r] + (long long) qqneg[l] * ppneg[r];
}
}
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 build(int *aa, int n) {
int i, x;
h_ = 0;
while (1 << h_ < n)
h_++;
n_ = 1 << h_;
for (i = 0; i < n_; i++)
aa_[i] = 1, bb_[i] = 0;
for (i = 0; i < n_ * 2; i++)
aa_[n_ + i] = 0, bb_[n_ + i] = i < n ? aa[i] : 0;
for (i = 0; i < n_; i++) {
sz[n_ + i] = 1;
x = i + 1 < n ? sgn(aa[i + 1] - aa[i]) * (i % 2 == 0 ? 1 : -1) : 0;
if (x == 1)
pppos[n_ + i] = 1, ppneg[n_ + i] = 0, qqpos[n_ + i] = 1, qqneg[n_ + i] = 0, st[n_ + i] = 1;
else if (x == -1)
pppos[n_ + i] = 0, ppneg[n_ + i] = 1, qqpos[n_ + i] = 0, qqneg[n_ + i] = 1, st[n_ + i] = 1;
else
pppos[n_ + i] = 0, ppneg[n_ + i] = 0, qqpos[n_ + i] = 0, qqneg[n_ + i] = 0, st[n_ + i] = 0;
}
for (i = n_ - 1; i > 0; i--)
sz[i] = sz[i << 1 | 0] + sz[i << 1 | 1], pul_(i);
}
void update(int l, int r, int a, long long b) {
push(l += n_), push(r += n_);
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
put(l++, a, b);
if ((r & 1) == 0)
put(r--, a, b);
}
}
long long query(int i) {
push(i += n_);
return bb_[i];
}
void upd_(int i, int x) {
i += n_;
push_(i);
if (x == 1)
pppos[i] = 1, ppneg[i] = 0, qqpos[i] = 1, qqneg[i] = 0, st[i] = 1;
else if (x == -1)
pppos[i] = 0, ppneg[i] = 1, qqpos[i] = 0, qqneg[i] = 1, st[i] = 1;
else
pppos[i] = 0, ppneg[i] = 0, qqpos[i] = 0, qqneg[i] = 0, st[i] = 0;
pull_(i);
}
void update_(int l, int r) {
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++);
if ((r & 1) == 0)
put_(r--);
}
pull_(l_), pull_(r_);
}
long long query_(int l, int r) {
int qpos, qneg, ppos, pneg;
long long x;
if (l > r)
return 0;
push_(l += n_), push_(r += n_);
qpos = 0, qneg = 0, ppos = 0, pneg = 0, x = 0;
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1) {
x += st[l] + (long long) qpos * pppos[l] + (long long) qneg * ppneg[l];
qpos = qqpos[l] < sz[l] ? qqpos[l] : qpos + sz[l];
qneg = qqneg[l] < sz[l] ? qqneg[l] : qneg + sz[l];
l++;
}
if ((r & 1) == 0) {
x += st[r] + (long long) qqpos[r] * ppos + (long long) qqneg[r] * pneg;
ppos = pppos[r] < sz[r] ? pppos[r] : sz[r] + ppos;
pneg = ppneg[r] < sz[r] ? ppneg[r] : sz[r] + pneg;
r--;
}
}
x += (long long) qpos * ppos + (long long) qneg * pneg;
return x;
}
int main() {
static int aa[N];
int n, q, i;
scanf("%d%d", &n, &q);
for (i = 0; i < n; i++)
scanf("%d", &aa[i]);
build(aa, n);
while (q--) {
static char s[2];
int l, r, x;
scanf("%s%d%d", s, &l, &r), l--, r--;
if (s[0] == '*') {
update(l, r, -1, 0);
if (l > 0)
upd_(l - 1, sgn(query(l) - query(l - 1)) * ((l - 1) % 2 == 0 ? 1 : -1));
update_(l, r - 1);
if (r + 1 < n)
upd_(r, sgn(query(r + 1) - query(r)) * (r % 2 == 0 ? 1 : -1));
} else if (s[0] == '+') {
scanf("%d", &x);
update(l, r, 1, x);
if (l > 0)
upd_(l - 1, sgn(query(l) - query(l - 1)) * ((l - 1) % 2 == 0 ? 1 : -1));
if (r + 1 < n)
upd_(r, sgn(query(r + 1) - query(r)) * (r % 2 == 0 ? 1 : -1));
} else
printf("%lld\n", query_(l, r - 1) + r - l + 1);
}
return 0;
}
Compilation message
Main.c: In function 'main':
Main.c:166:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | scanf("%d%d", &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~
Main.c:168:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
168 | scanf("%d", &aa[i]);
| ^~~~~~~~~~~~~~~~~~~
Main.c:174:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
174 | scanf("%s%d%d", s, &l, &r), l--, r--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:183:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
183 | scanf("%d", &x);
| ^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1252 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1204 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1204 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1108 KB |
Output is correct |
| 6 |
Correct |
1 ms |
412 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
37 ms |
28456 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1252 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1204 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1204 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1108 KB |
Output is correct |
| 6 |
Correct |
1 ms |
412 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1244 KB |
Output is correct |
| 8 |
Correct |
159 ms |
14452 KB |
Output is correct |
| 9 |
Correct |
158 ms |
14512 KB |
Output is correct |
| 10 |
Correct |
157 ms |
15564 KB |
Output is correct |
| 11 |
Correct |
344 ms |
15044 KB |
Output is correct |
| 12 |
Correct |
154 ms |
15532 KB |
Output is correct |
| 13 |
Correct |
155 ms |
15484 KB |
Output is correct |
| 14 |
Correct |
149 ms |
15532 KB |
Output is correct |
| 15 |
Correct |
157 ms |
14552 KB |
Output is correct |
| 16 |
Correct |
197 ms |
15548 KB |
Output is correct |
| 17 |
Correct |
145 ms |
15468 KB |
Output is correct |
| 18 |
Correct |
85 ms |
15356 KB |
Output is correct |
| 19 |
Correct |
102 ms |
15352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1252 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1204 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1204 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1108 KB |
Output is correct |
| 6 |
Correct |
1 ms |
412 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1244 KB |
Output is correct |
| 8 |
Runtime error |
37 ms |
28456 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
