Submission #2551579
Source Code Expand
#include <algorithm>
#include <cstring>
#include <cstdio>
struct point
{
int x, y;
inline bool operator <(const point &a) const
{
return x < a.x;
}
} arr[300005], st1[300005], st2[300005];
int mx[1200005], lazy[1200005];
void modify(int u, int l, int r, int L, int R, int x)
{
if (L <= l && r <= R)
{
mx[u] += x;
lazy[u] += x;
return;
}
int m = l + r >> 1;
if (L <= m)
modify(u << 1, l, m, L, R, x);
if (m < R)
modify(u << 1 | 1, m + 1, r, L, R, x);
mx[u] = std::max(mx[u << 1], mx[u << 1 | 1]) + lazy[u];
}
int work(int w, int h, int n)
{
memset(mx, -0x3f, sizeof(mx));
memset(lazy, 0, sizeof(lazy));
std::sort(arr, arr + n);
int tp1 = 0, tp2 = 0, ans = 0;
for (int i = 0; i < n - 1; i++)
{
int &tp = arr[i].y <= h / 2 ? tp1 : tp2, nxt = i - 1;
auto *st = arr[i].y <= h / 2 ? st1 : st2;
while (tp && ((st[tp - 1].y < arr[i].y) ^ (arr[i].y > h / 2)))
{
modify(1, 0, n - 1, st[tp - 1].x, nxt, (st[tp - 1].y - arr[i].y) * (arr[i].y <= h / 2 ? 1 : -1));
nxt = st[--tp].x - 1;
}
if (nxt != i - 1)
st[tp++] = {nxt + 1, arr[i].y};
st1[tp1++] = {i, 0};
st2[tp2++] = {i, h};
modify(1, 0, n - 1, i, i, h - arr[i].x - mx[0]);
ans = std::max(ans, mx[1] + arr[i + 1].x);
}
return ans;
}
int main()
{
// freopen("ARC063-F.in", "r", stdin);
int w, h, n;
scanf("%d%d%d", &w, &h, &n);
for (int i = 0; i < n; i++)
scanf("%d%d", &arr[i].x, &arr[i].y);
arr[n++] = {0, 0};
arr[n++] = {w, h};
int ans = work(w, h, n);
for (int i = 0; i < n; i++)
std::swap(arr[i].x, arr[i].y);
ans = std::max(ans, work(h, w, n));
printf("%d\n", ans << 1);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Snuke's Coloring 2 |
User |
diamond_duke |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
1706 Byte |
Status |
AC |
Exec Time |
512 ms |
Memory |
16640 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:56:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &w, &h, &n);
^
./Main.cpp:58:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &arr[i].x, &arr[i].y);
^
Judge Result
Set Name |
sample |
All |
Score / Max Score |
0 / 0 |
1600 / 1600 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All |
dia_01.txt, dia_02.txt, dia_03.txt, dia_04.txt, dial_01.txt, dial_02.txt, dial_03.txt, dial_04.txt, dial_05.txt, dial_06.txt, dialr_01.txt, dialr_02.txt, dialr_03.txt, dialr_04.txt, diar_01.txt, diar_02.txt, diar_03.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, poc_t_1.txt, poc_t_2.txt, poc_t_3.txt, poc_t_4.txt, poc_t_5.txt, poc_w_1.txt, poc_w_2.txt, random0_01.txt, random0_02.txt, random0_03.txt, random1_01.txt, random1_02.txt, random1_03.txt, random1_04.txt, random1_05.txt, random1_06.txt, random1_07.txt, rect_01.txt, rect_02.txt, rect_03.txt, rect_04.txt, rect_05.txt, rect_06.txt, rect_07.txt, rect_08.txt, rect_09.txt, rect_10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, x_01.txt, x_02.txt, x_03.txt, x_04.txt |
Case Name |
Status |
Exec Time |
Memory |
dia_01.txt |
AC |
508 ms |
16512 KB |
dia_02.txt |
AC |
507 ms |
16512 KB |
dia_03.txt |
AC |
508 ms |
16512 KB |
dia_04.txt |
AC |
512 ms |
16512 KB |
dial_01.txt |
AC |
489 ms |
16512 KB |
dial_02.txt |
AC |
500 ms |
16512 KB |
dial_03.txt |
AC |
492 ms |
16512 KB |
dial_04.txt |
AC |
504 ms |
16512 KB |
dial_05.txt |
AC |
494 ms |
16512 KB |
dial_06.txt |
AC |
493 ms |
16512 KB |
dialr_01.txt |
AC |
464 ms |
16512 KB |
dialr_02.txt |
AC |
468 ms |
16512 KB |
dialr_03.txt |
AC |
468 ms |
16512 KB |
dialr_04.txt |
AC |
466 ms |
16512 KB |
diar_01.txt |
AC |
494 ms |
16512 KB |
diar_02.txt |
AC |
493 ms |
16512 KB |
diar_03.txt |
AC |
495 ms |
16512 KB |
hand_01.txt |
AC |
5 ms |
14464 KB |
hand_02.txt |
AC |
5 ms |
14464 KB |
hand_03.txt |
AC |
5 ms |
14464 KB |
hand_04.txt |
AC |
5 ms |
14464 KB |
hand_05.txt |
AC |
5 ms |
14464 KB |
poc_t_1.txt |
AC |
4 ms |
14464 KB |
poc_t_2.txt |
AC |
5 ms |
14464 KB |
poc_t_3.txt |
AC |
4 ms |
14464 KB |
poc_t_4.txt |
AC |
5 ms |
14464 KB |
poc_t_5.txt |
AC |
4 ms |
14464 KB |
poc_w_1.txt |
AC |
5 ms |
14464 KB |
poc_w_2.txt |
AC |
5 ms |
14464 KB |
random0_01.txt |
AC |
466 ms |
16512 KB |
random0_02.txt |
AC |
467 ms |
16512 KB |
random0_03.txt |
AC |
471 ms |
16512 KB |
random1_01.txt |
AC |
465 ms |
16512 KB |
random1_02.txt |
AC |
465 ms |
16512 KB |
random1_03.txt |
AC |
469 ms |
16512 KB |
random1_04.txt |
AC |
471 ms |
16512 KB |
random1_05.txt |
AC |
470 ms |
16512 KB |
random1_06.txt |
AC |
465 ms |
16512 KB |
random1_07.txt |
AC |
465 ms |
16512 KB |
rect_01.txt |
AC |
464 ms |
16512 KB |
rect_02.txt |
AC |
464 ms |
16512 KB |
rect_03.txt |
AC |
465 ms |
16640 KB |
rect_04.txt |
AC |
438 ms |
16512 KB |
rect_05.txt |
AC |
463 ms |
16512 KB |
rect_06.txt |
AC |
444 ms |
16512 KB |
rect_07.txt |
AC |
464 ms |
16512 KB |
rect_08.txt |
AC |
464 ms |
16512 KB |
rect_09.txt |
AC |
464 ms |
16512 KB |
rect_10.txt |
AC |
465 ms |
16512 KB |
sample_01.txt |
AC |
5 ms |
14464 KB |
sample_02.txt |
AC |
5 ms |
14464 KB |
sample_03.txt |
AC |
5 ms |
14464 KB |
sample_04.txt |
AC |
4 ms |
14464 KB |
x_01.txt |
AC |
402 ms |
16512 KB |
x_02.txt |
AC |
402 ms |
16512 KB |
x_03.txt |
AC |
402 ms |
16512 KB |
x_04.txt |
AC |
412 ms |
16512 KB |