| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 486379 |
2021-11-11T13:21:45 Z |
rainboy |
Ruka (COI15_ruka) |
C |
|
550 ms |
10300 KB |
#include <stdio.h>
#define N 100000
#define Q 300000
#define N_ (1 + (N * 2 + Q * 4) * 2)
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int zz[N_], ll[N_], rr[N_], xx[N_], cc[N_], sum[N_], u_, l_, r_;
int node(int x, int c) {
static int _ = 1;
zz[_] = rand_();
xx[_] = x, sum[_] = cc[_] = c;
return _++;
}
void pul(int u) {
sum[u] = cc[u] + sum[ll[u]] + sum[rr[u]];
}
void split(int u, int x) {
if (u == 0) {
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;
}
}
int tr_add(int t, int x, int c) {
split(t, x);
if (u_ == 0)
u_ = node(x, 0);
if ((cc[u_] += c) == 0)
u_ = 0;
pul(u_);
t = merge(merge(l_, u_), r_);
return t;
}
int add(int t, int x1, int x2, int c) {
if (x1 != x2 && c != 0) {
int tmp;
if (x1 > x2)
tmp = x1, x1 = x2, x2 = tmp;
t = tr_add(t, x1, c), t = tr_add(t, x2, -c);
}
return t;
}
int query(int t, int x) {
int c = 0;
while (t)
if (xx[t] <= x)
c += sum[ll[t]] + cc[t], t = rr[t];
else
t = ll[t];
return c;
}
int main() {
static int xx[N], yy[N], xxp[N + 1], yyp[N + 1], xxq[N + 1], yyq[N + 1];
int n, m, i, x, y, tx, ty, p, q;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[i], &yy[i]);
scanf("%d", &m);
x = 0, y = 0, tx = 0, ty = 0;
for (i = n - 1; i >= 0; i--) {
xxq[i] = x, yyq[i] = y, x += xx[i], y += yy[i];
tx = add(tx, xxq[i], xxq[i] + xx[i], 1), ty = add(ty, yyq[i], yyq[i] + yy[i], 1);
}
x++, y++;
xxp[0] = 1, yyp[0] = 1;
i = 0, p = 0, q = query(tx, x) + query(ty, y);
while (m--) {
static char s[2];
scanf("%s", s);
if (s[0] == 'B') {
if (i > 0) {
i--;
if ((xxp[i] > 0) != (xxp[i] + xx[i] > 0))
p--;
if ((yyp[i] > 0) != (yyp[i] + yy[i] > 0))
p--;
xxq[i] = xxq[i + 1] + xx[i + 1], yyq[i] = yyq[i + 1] + yy[i + 1];
tx = add(tx, xxq[i], xxq[i] + xx[i], 1), ty = add(ty, yyq[i], yyq[i] + yy[i], 1);
q = query(tx, x) + query(ty, y);
}
} else if (s[0] == 'F') {
if (i + 1 < n) {
tx = add(tx, xxq[i], xxq[i] + xx[i], -1), ty = add(ty, yyq[i], yyq[i] + yy[i], -1);
if ((xxp[i] > 0) != (xxp[i] + xx[i] > 0))
p++;
if ((yyp[i] > 0) != (yyp[i] + yy[i] > 0))
p++;
i++;
xxp[i] = xxp[i - 1] + xx[i - 1], yyp[i] = yyp[i - 1] + yy[i - 1];
q = query(tx, x) + query(ty, y);
}
} else if (s[0] == 'C') {
int x_, y_;
scanf("%d%d", &x_, &y_);
tx = add(tx, xxq[i], xxq[i] + xx[i], -1), ty = add(ty, yyq[i], yyq[i] + yy[i], -1);
x += x_ - xx[i], y += y_ - yy[i], xx[i] = x_, yy[i] = y_;
tx = add(tx, xxq[i], xxq[i] + xx[i], 1), ty = add(ty, yyq[i], yyq[i] + yy[i], 1);
q = query(tx, x) + query(ty, y);
} else
printf("%d\n", p + q);
}
return 0;
}
Compilation message
ruka.c: In function 'main':
ruka.c:96:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
ruka.c:98:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.c:99:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%d", &m);
| ^~~~~~~~~~~~~~~
ruka.c:111:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | scanf("%s", s);
| ^~~~~~~~~~~~~~
ruka.c:137:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf("%d%d", &x_, &y_);
| ^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
167 ms |
2344 KB |
Output is correct |
| 6 |
Correct |
147 ms |
3316 KB |
Output is correct |
| 7 |
Correct |
148 ms |
2688 KB |
Output is correct |
| 8 |
Correct |
149 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
167 ms |
2344 KB |
Output is correct |
| 6 |
Correct |
147 ms |
3316 KB |
Output is correct |
| 7 |
Correct |
148 ms |
2688 KB |
Output is correct |
| 8 |
Correct |
149 ms |
2636 KB |
Output is correct |
| 9 |
Correct |
470 ms |
10300 KB |
Output is correct |
| 10 |
Correct |
550 ms |
10188 KB |
Output is correct |
| 11 |
Correct |
401 ms |
8072 KB |
Output is correct |
| 12 |
Correct |
462 ms |
10272 KB |
Output is correct |
