#include <stdio.h>
#include <string.h>
#define N 150000
#define M 30000
#define INF 0x3f3f3f3f3f3f3f3fLL
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
long long dd[N + 2]; int hh[N + 2], iq[1 + N + 2], pq[N + 2], cnt;
int lt(int i, int j) {
return dd[i] > dd[j] || dd[i] == dd[j] && hh[i] < hh[j];
}
int p2(int p) {
return (p *= 2) > cnt ? 0 : p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p;
}
void pq_up(int i) {
int p, q, j;
for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int p, q, j;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add(int i) {
pq[i] = ++cnt, pq_up(i);
}
int pq_first() { return iq[1]; }
void pq_remove(int i) {
if (pq[i]) {
int j = iq[cnt--];
if (j != i)
pq[j] = pq[i], pq_up(j), pq_dn(j);
pq[i] = 0;
}
}
int bb[N], n;
void add(int l, int r) {
if (l == -1 || r == -1)
return;
if (l == n) {
if (r == 0)
return;
if (r == n + 1)
dd[l] = INF, hh[l] = 0 * 2 + 0;
else if ((bb[r] & 1) == 0)
dd[l] = (long long) r * r + 1, hh[l] = 0 * 2 + 0;
else if ((bb[r] & 2) == 0)
dd[l] = (long long) r * r + 1, hh[l] = 0 * 2 + 1;
else
dd[l] = (long long) r * r, hh[l] = 0 * 2 + 0;
} else if (r == n + 1) {
if (l == n - 1 && bb[l] == 3)
return;
if ((bb[l] & 1) == 0)
dd[l] = (long long) (n - 1 - l) * (n - 1 - l) + 1, hh[l] = (n - 1) * 2 + 0;
else if ((bb[l] & 2) == 0)
dd[l] = (long long) (n - 1 - l) * (n - 1 - l) + 1, hh[l] = (n - 1) * 2 + 1;
else
dd[l] = (long long) (n - 1 - l) * (n - 1 - l), hh[l] = (n - 1) * 2 + 0;
} else {
int l_, r_, i, j, h;
long long d_;
if (l + 1 == r && bb[l] == 3)
return;
l_ = max((l + r) / 2 - 3, l), r_ = min((l + r) / 2 + 3, r - 1), d_ = -1, h = -1;
for (i = l_; i <= r_; i++)
for (j = 0; j < 2; j++) {
long long d;
d = INF;
if ((bb[l] & 1) != 0)
d = min(d, (long long) (l - i) * (l - i) + 0);
if ((bb[l] & 2) != 0)
d = min(d, (long long) (l - i) * (l - i) + 1);
if ((bb[r] & 1) != 0)
d = min(d, (long long) (r - i) * (r - i) + 0);
if ((bb[r] & 2) != 0)
d = min(d, (long long) (r - i) * (r - i) + 1);
if (d_ < d)
d_ = d, h = i * 2 + 0;
d = INF;
if ((bb[l] & 1) != 0)
d = min(d, (long long) (l - i) * (l - i) + 1);
if ((bb[l] & 2) != 0)
d = min(d, (long long) (l - i) * (l - i) + 0);
if ((bb[r] & 1) != 0)
d = min(d, (long long) (r - i) * (r - i) + 1);
if ((bb[r] & 2) != 0)
d = min(d, (long long) (r - i) * (r - i) + 0);
if (d_ < d)
d_ = d, h = i * 2 + 1;
}
dd[l] = d_, hh[l] = h;
}
pq_add(l);
}
int main() {
static int pp[N + 2], qq[N + 2], hh_[M];
int m, k, g;
scanf("%d%d", &n, &m);
memset(pp, -1, (n + 2) * sizeof *pp);
memset(qq, -1, (n + 2) * sizeof *qq);
qq[n] = n + 1, pp[n + 1] = n;
add(n, n + 1);
k = 0;
for (g = 0; g < m; g++) {
static char s[2];
int h, i, j;
scanf("%s", s);
if (s[0] == 'E') {
int l, r;
l = pq_first(), pq_remove(l), r = qq[l];
hh_[g] = h = hh[l], i = h / 2, j = h % 2;
printf("%d %d\n", i + 1, j + 1);
if (i == l) {
if (pp[l] != -1)
pq_remove(pp[l]);
} else {
pp[i] = l, qq[i] = r;
if (l != -1)
qq[l] = i;
if (r != -1)
pp[r] = i;
}
bb[i] ^= 1 << j, add(pp[i], i), add(i, qq[i]);
} else {
int g_;
scanf("%d", &g_), g_--;
h = hh_[g_], i = h / 2, j = h % 2;
if (pp[i] != -1)
pq_remove(pp[i]);
pq_remove(i);
if ((bb[i] ^= (1 << j)) == 0) {
if (pp[i] != -1)
qq[pp[i]] = qq[i];
if (qq[i] != -1)
pp[qq[i]] = pp[i];
add(pp[i], qq[i]);
} else
add(pp[i], i), add(i, qq[i]);
}
}
return 0;
}
Compilation message
tram.c: In function 'lt':
tram.c:14:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
14 | return dd[i] > dd[j] || dd[i] == dd[j] && hh[i] < hh[j];
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
tram.c: In function 'main':
tram.c:119:9: warning: variable 'k' set but not used [-Wunused-but-set-variable]
119 | int m, k, g;
| ^
tram.c:121:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
tram.c:131:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
131 | scanf("%s", s);
| ^~~~~~~~~~~~~~
tram.c:152:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | scanf("%d", &g_), g_--;
| ^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
404 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
420 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
288 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4404 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4400 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4308 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
1140 KB |
Output is correct |
| 2 |
Correct |
14 ms |
596 KB |
Output is correct |
| 3 |
Correct |
15 ms |
1032 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
4884 KB |
Output is correct |
| 2 |
Correct |
11 ms |
664 KB |
Output is correct |
| 3 |
Correct |
17 ms |
4772 KB |
Output is correct |
