This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <string.h>
#define N 200000
#define N_ (1 << 18) /* N_ = pow2(ceil(log2(N))) */
int max(int a, int b) { return a > b ? a : b; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[N], yy[N], n;
int compare_y(int i, int j) {
return yy[i] - yy[j];
}
int compare_xy(int i, int j) {
return xx[i] != xx[j] ? xx[i] - xx[j] : yy[i] - yy[j];
}
int (*compare)(int, int);
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int yy1[N], n1;
int sz[N_ * 2];
int ss1[N_ * 2], ss2[N_ * 2];
int ccp[N_ * 2], ssp[N_ * 2];
int ccq[N_ * 2], ssq[N_ * 2];
char good[N_ * 2]; char lz[N_ * 2];
int h_, n_;
int flip(int c) {
return c == 0 ? 0 : (c < 0 ? (c == -1 ? -2 : -1) : (c == 1 ? 2 : 1));
}
void put(int i, int x) {
int tmp;
if (x == -1) {
tmp = ss1[i], ss1[i] = ss2[i], ss2[i] = tmp;
ccp[i] = flip(ccp[i]), ccq[i] = flip(ccq[i]);
if (i < n_)
lz[i] = flip(lz[i]);
} else if (x != -2) {
if (x == 0)
ss1[i] = ss2[i] = 0;
else if (x == 1)
ss1[i] = sz[i];
else
ss2[i] = sz[i];
ccp[i] = ccq[i] = x, ssp[i] = ssq[i] = x == 0 ? 0 : sz[i];
good[i] = 1;
if (i < n_)
lz[i] = x;
}
}
void pus(int i) {
if (lz[i] != -2)
put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = -2;
}
void pul(int i) {
if (lz[i] == -2) {
int l = i << 1, r = l | 1;
ss1[i] = ss1[l] + ss1[r], ss2[i] = ss2[l] + ss2[r];
ccp[i] = ccp[l];
if (ccp[l] == 0)
ssp[i] = 0;
else
ssp[i] = ssp[l] < sz[l] || ccp[r] != ccp[l] ? ssp[l] : sz[l] + ssp[r];
ccq[i] = ccq[r];
if (ccq[r] == 0)
ssq[i] = 0;
else
ssq[i] = ssq[r] < sz[r] || ccq[l] != ccq[r] ? ssq[r] : ssq[l] + sz[r];
good[i] = good[l] && good[r] && (ccq[l] != ccp[r] ? (ssq[l] == sz[l] || ssq[l] % 2 == 0) && (ssp[r] == sz[r] || ssp[r] % 2 == 0) : ssq[l] == sz[l] || ssp[r] == sz[r] || (ssq[l] + ssp[r]) % 2 == 0);
}
}
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 update(int l, int r, int x) {
int l_ = l += n_, r_ = r += n_;
push(l_), push(r_);
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
put(l++, x);
if ((r & 1) == 0)
put(r--, x);
}
pull(l_), pull(r_);
}
int query(int l, int r) {
int s, s1, s2;
s = r - l + 1;
push(l += n_), push(r += n_);
s1 = s2 = 0;
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
s1 += ss1[l], s2 += ss2[l], l++;
if ((r & 1) == 0)
s1 += ss1[r], s2 += ss2[r], r--;
}
return s1 == 0 && s2 == 0 ? 1 : (s1 == s ? 0 : -1);
}
void build() {
int i;
h_ = 0;
while (1 << h_ < n1)
h_++;
n_ = 1 << h_;
memset(lz, -2, n_ * sizeof *lz);
memset(good, 1, n_ * 2 * sizeof *good);
for (i = 0; i + 1 < n1; i++)
sz[n_ + i] = yy1[i + 1] - yy1[i];
for (i = n_ - 1; i > 0; i--)
sz[i] = sz[i << 1 | 0] + sz[i << 1 | 1], pul(i);
}
int main() {
static int ii[N], xx_[N], yy_[N];
int i, j, x1, x2, y, y1, y2, ans, t;
scanf("%d%*d", &n);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[i], &yy[i]);
n1 = 0;
for (i = 0; i < n; i++)
if ((xx[i] != xx[(i + 1) % n]) != (xx[i] != xx[(i - 1 + n) % n]))
xx_[n1] = xx[i], yy_[n1] = yy[i], n1++;
memcpy(xx, xx_, n1 * sizeof *xx_), memcpy(yy, yy_, n1 * sizeof *yy_), n = n1;
for (i = 0; i < n; i++)
ii[i] = i;
compare = compare_y, sort(ii, 0, n);
n1 = 0;
for (i = 0; i < n; i = j) {
j = i, y = yy[ii[i]];
while (j < n && yy[ii[j]] == y)
yy[ii[j++]] = n1;
yy1[n1++] = y;
}
build(n1);
compare = compare_xy, sort(ii, 0, n);
ans = 0;
for (i = 0; i + 1 < n; i += 2) {
y1 = yy[ii[i]], y2 = yy[ii[i + 1]];
t = query(y1, y2 - 1);
if (t == -1)
break;
update(y1, y2 - 1, t);
if (i + 2 == n || xx[ii[i + 2]] != xx[ii[i + 1]]) {
x1 = xx[ii[i + 1]], x2 = xx[ii[i + 2]];
if (!good[1] || ssp[1] % 2 != 0 || ssq[1] % 2 != 0)
break;
if (ss2[1] == 0)
ans = max(ans, x1 + (x2 - x1) / 2 * 2);
if (ss1[1] == 0)
ans = max(ans, x1 + 1 + (x2 - x1 - 1) / 2 * 2);
if ((x2 - x1) % 2 != 0)
put(1, -1);
}
}
printf("%d\n", ans);
return 0;
}
Compilation message (stderr)
Main.c: In function 'main':
Main.c:167:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | scanf("%d%*d", &n);
| ^~~~~~~~~~~~~~~~~~
Main.c:169:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |