Submission #2554411
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define M 200010
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
struct Node{
int x, y;
inline bool operator < (const Node& rhs) const {
return x < rhs.x || (x == rhs.x && y < rhs.y);
}
} a[M], L[M], R[M];
int lz[M * 4], mx[M * 4];
int w, h, n;
int Ans;
inline void build(int l, int r, int o) {
lz[o] = 0; mx[o] = -1e9;
if(l == r) return;
int mid = (l + r) / 2;
build(l, mid, 2 * o);
build(mid + 1, r, 2 * o + 1);
}
inline void update(int o, int x) {
mx[o] += x; lz[o] += x;
}
inline void pushdown(int l, int r, int o) {
if(lz[o]) {
update(2 * o, lz[o]);
update(2 * o + 1, lz[o]);
lz[o] = 0;
}
}
inline void change(int l, int r, int o, int x, int y, int z) {
if(x <= l && r <= y) {
update(o, z);
return;
}
pushdown(l, r, o);
int mid = (l + r) / 2;
if(x <= mid) change(l, mid, 2 * o, x, y, z);
if(y > mid) change(mid + 1, r, 2 * o + 1, x, y, z);
mx[o] = max(mx[2 * o], mx[2 * o + 1]);
}
inline void Do() {
build(1, n, 1);
sort(a + 1, a + n + 1);
int t1 = 0, t2 = 0;
for(int i = 1; i < n; ++ i) {
//cerr << i << endl;
if(a[i].y <= h / 2) {
//if(i == 3) puts("fuck");
int lst = i - 1;
while(t1 && a[i].y > L[t1].y) {
//if(i == 3) printf("%d %d\n", L[t1].x, lst);
change(1, n, 1, L[t1].x, lst, L[t1].y - a[i].y);
lst = L[t1].x - 1; -- t1;
}
if(lst != i - 1) L[++ t1] = (Node){lst + 1, a[i].y};
}
else {
int lst = i - 1;
while(t2 && a[i].y < R[t2].y) {
change(1, n, 1, R[t2].x, lst, a[i].y - R[t2].y);
lst = R[t2].x - 1; -- t2;
}
if(lst != i - 1) R[++ t2] = (Node){lst + 1, a[i].y};
}
L[++ t1] = (Node){i, 0};
R[++ t2] = (Node){i, h};
change(1, n, 1, i, i, 1e9 + h - a[i].x);
Ans = max(Ans, mx[1] + a[i + 1].x);
}
}
int main() {
//freopen("a.in", "r", stdin);
w = read(), h = read(), n = read();
for(int i = 1; i <= n; ++ i) {
a[i] = (Node){read(), read()};
}
a[++ n] = (Node){0, 0};
a[++ n] = (Node){w, h};
//cerr << 233 << endl;
Do();
for(int i = 1; i <= n; ++ i) {
swap(a[i].x, a[i].y);
}
swap(w, h);
//cerr << 233 << endl;
Do();
printf("%d\n", Ans * 2);
}
Submission Info
Submission Time |
|
Task |
F - Snuke's Coloring 2 |
User |
iamqzh |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2402 Byte |
Status |
RE |
Exec Time |
127 ms |
Memory |
6400 KB |
Judge Result
Set Name |
sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
RE |
118 ms |
3072 KB |
dia_02.txt |
RE |
118 ms |
2944 KB |
dia_03.txt |
RE |
118 ms |
2944 KB |
dia_04.txt |
RE |
122 ms |
3072 KB |
dial_01.txt |
RE |
118 ms |
3072 KB |
dial_02.txt |
RE |
120 ms |
2944 KB |
dial_03.txt |
RE |
121 ms |
2944 KB |
dial_04.txt |
RE |
123 ms |
2944 KB |
dial_05.txt |
RE |
124 ms |
2944 KB |
dial_06.txt |
RE |
127 ms |
3072 KB |
dialr_01.txt |
RE |
118 ms |
3072 KB |
dialr_02.txt |
RE |
118 ms |
2944 KB |
dialr_03.txt |
RE |
120 ms |
3072 KB |
dialr_04.txt |
RE |
119 ms |
2944 KB |
diar_01.txt |
RE |
118 ms |
2944 KB |
diar_02.txt |
RE |
120 ms |
2944 KB |
diar_03.txt |
RE |
122 ms |
2944 KB |
hand_01.txt |
AC |
2 ms |
6400 KB |
hand_02.txt |
AC |
2 ms |
6400 KB |
hand_03.txt |
AC |
2 ms |
6400 KB |
hand_04.txt |
AC |
2 ms |
6400 KB |
hand_05.txt |
AC |
2 ms |
6400 KB |
poc_t_1.txt |
AC |
2 ms |
6400 KB |
poc_t_2.txt |
AC |
2 ms |
6400 KB |
poc_t_3.txt |
AC |
2 ms |
6400 KB |
poc_t_4.txt |
AC |
2 ms |
6400 KB |
poc_t_5.txt |
AC |
2 ms |
6400 KB |
poc_w_1.txt |
AC |
2 ms |
6400 KB |
poc_w_2.txt |
AC |
2 ms |
6400 KB |
random0_01.txt |
RE |
118 ms |
2944 KB |
random0_02.txt |
RE |
117 ms |
3072 KB |
random0_03.txt |
RE |
123 ms |
3072 KB |
random1_01.txt |
RE |
118 ms |
2944 KB |
random1_02.txt |
RE |
118 ms |
3072 KB |
random1_03.txt |
RE |
120 ms |
3072 KB |
random1_04.txt |
RE |
120 ms |
2944 KB |
random1_05.txt |
RE |
124 ms |
3072 KB |
random1_06.txt |
RE |
120 ms |
3072 KB |
random1_07.txt |
RE |
119 ms |
3072 KB |
rect_01.txt |
RE |
119 ms |
3072 KB |
rect_02.txt |
RE |
118 ms |
3072 KB |
rect_03.txt |
RE |
119 ms |
3072 KB |
rect_04.txt |
RE |
124 ms |
2944 KB |
rect_05.txt |
RE |
119 ms |
3072 KB |
rect_06.txt |
RE |
119 ms |
2944 KB |
rect_07.txt |
RE |
118 ms |
3072 KB |
rect_08.txt |
RE |
118 ms |
3072 KB |
rect_09.txt |
RE |
119 ms |
2944 KB |
rect_10.txt |
RE |
121 ms |
2944 KB |
sample_01.txt |
AC |
2 ms |
6400 KB |
sample_02.txt |
AC |
2 ms |
6400 KB |
sample_03.txt |
AC |
2 ms |
6400 KB |
sample_04.txt |
AC |
2 ms |
6400 KB |
x_01.txt |
RE |
118 ms |
2944 KB |
x_02.txt |
RE |
117 ms |
3072 KB |
x_03.txt |
RE |
118 ms |
3072 KB |
x_04.txt |
RE |
121 ms |
3072 KB |