Submission #1372332
Source Code Expand
#include <bits/stdc++.h>
#define lc rt << 1
#define rc rt << 1 | 1
using namespace std;
const int N = 6e5, M = N << 2;
inline int read()
{
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
struct P
{
int x, y;
}p[N],st1[N],st2[N];
bool cmpx(const P &a,const P &b)
{
return a.x < b.x;
}
int x[N], ans, mx[M], tag[M];
void build(int rt, int l, int r)
{
mx[rt] = -1 << 30;
tag[rt] = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
}
void modify(int rt,int l,int r,int L,int R,int d)
{
if (L <= l && r <= R) tag[rt] += d, mx[rt] += d;
else
{
int mid = (l + r) >> 1;
if (tag[rt])
{
mx[lc] += tag[rt], tag[lc] += tag[rt];
mx[rc] += tag[rt], tag[rc] += tag[rt];
tag[rt] = 0;
}
if (L <= mid) modify(lc, l, mid, L, R, d);
if (mid < R) modify(rc, mid + 1, r, L, R, d);
mx[rt] = max(mx[lc], mx[rc]);
}
}
void add(int rt, int l, int r, int k, int d)
{
if (l == r) {mx[rt] = d; return;}
int mid = (l + r) >> 1;
if(k <= mid) add(lc, l, mid, k, d);
else add(rc, mid + 1, r, k, d);
mx[rt] = max(mx[lc], mx[rc]);
}
void solve(int n, int m, int T)
{
int len = T, l1, l2, a, b, e, l, r, mid;
P *st;
sort(p + 1, p + 1 + T, cmpx);
for (int i = 1; i <= T; i ++)
x[i] = p[i].x;
p[++ T] = (P){n, m >> 1};
x[++ len] = 0;
x[++ len] = n;
sort(x + 1, x + 1 + len);
len = unique(x + 1, x + 1 + len) - x - 1;
build(1, 1, len);
add(1, 1, len, 1, m);
st1[l1 = 1] = st2[l2 = 1] = (P){1, m >> 1};
for (int i = 1; i <= T; i ++)
{
int &top = p[i].y <= m >> 1 ? (st = st1,l1) : (st = st2, l2);
a = p[i].x, b = abs(p[i].y - (m >> 1));
for (l = 1, r = len; l != r; a <= x[mid = (l + r) >> 1] ? r = mid : l = mid + 1);
a = l;
e = a;
ans = max(ans,x[a] + mx[1]);
add(1, 1, len,a,m-x[a]);
while (top && b < st[top].y)
{
if (st[top].x != e) modify(1, 1, len, st[top].x, e - 1, b - st[top].y);
e = st[top --].x;
}
if (e != a) st[++ top] = (P){e,b};
st[++ top] = (P){a, m >> 1};
if (p[i].y > m >> 1) st1[++ l1] = (P){a, m >> 1};
else st2[++ l2] = (P){a, m >> 1};
}
}
int main()
{
int n = read() << 1;
int m = read() << 1;
int T = read();
for (int i = 1; i <= T; i ++)
p[i].x = read() << 1, p[i].y = read() << 1;
solve(n, m, T);
for (int i = 1; i <= T; i ++)
swap(p[i].x,p[i].y);
solve(m, n, T);
printf("%d\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Snuke's Coloring 2 |
User |
wavelettree |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
2586 Byte |
Status |
AC |
Exec Time |
538 ms |
Memory |
26880 KB |
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 |
529 ms |
24832 KB |
dia_02.txt |
AC |
528 ms |
24832 KB |
dia_03.txt |
AC |
528 ms |
24832 KB |
dia_04.txt |
AC |
532 ms |
24832 KB |
dial_01.txt |
AC |
526 ms |
24832 KB |
dial_02.txt |
AC |
530 ms |
24832 KB |
dial_03.txt |
AC |
531 ms |
24832 KB |
dial_04.txt |
AC |
535 ms |
24832 KB |
dial_05.txt |
AC |
535 ms |
24832 KB |
dial_06.txt |
AC |
536 ms |
24832 KB |
dialr_01.txt |
AC |
501 ms |
24832 KB |
dialr_02.txt |
AC |
507 ms |
24832 KB |
dialr_03.txt |
AC |
504 ms |
24832 KB |
dialr_04.txt |
AC |
503 ms |
24832 KB |
diar_01.txt |
AC |
534 ms |
24832 KB |
diar_02.txt |
AC |
536 ms |
24832 KB |
diar_03.txt |
AC |
538 ms |
24832 KB |
hand_01.txt |
AC |
3 ms |
10496 KB |
hand_02.txt |
AC |
3 ms |
10496 KB |
hand_03.txt |
AC |
3 ms |
10496 KB |
hand_04.txt |
AC |
3 ms |
10496 KB |
hand_05.txt |
AC |
3 ms |
10496 KB |
poc_t_1.txt |
AC |
3 ms |
10496 KB |
poc_t_2.txt |
AC |
3 ms |
10496 KB |
poc_t_3.txt |
AC |
3 ms |
10496 KB |
poc_t_4.txt |
AC |
3 ms |
10496 KB |
poc_t_5.txt |
AC |
3 ms |
10496 KB |
poc_w_1.txt |
AC |
3 ms |
10496 KB |
poc_w_2.txt |
AC |
3 ms |
10496 KB |
random0_01.txt |
AC |
506 ms |
24832 KB |
random0_02.txt |
AC |
505 ms |
24832 KB |
random0_03.txt |
AC |
510 ms |
24832 KB |
random1_01.txt |
AC |
502 ms |
24832 KB |
random1_02.txt |
AC |
505 ms |
24832 KB |
random1_03.txt |
AC |
506 ms |
24832 KB |
random1_04.txt |
AC |
507 ms |
24832 KB |
random1_05.txt |
AC |
509 ms |
24832 KB |
random1_06.txt |
AC |
521 ms |
24832 KB |
random1_07.txt |
AC |
503 ms |
24832 KB |
rect_01.txt |
AC |
505 ms |
24832 KB |
rect_02.txt |
AC |
504 ms |
24832 KB |
rect_03.txt |
AC |
504 ms |
24832 KB |
rect_04.txt |
AC |
474 ms |
24832 KB |
rect_05.txt |
AC |
502 ms |
24832 KB |
rect_06.txt |
AC |
499 ms |
26880 KB |
rect_07.txt |
AC |
506 ms |
24832 KB |
rect_08.txt |
AC |
507 ms |
24832 KB |
rect_09.txt |
AC |
505 ms |
24832 KB |
rect_10.txt |
AC |
505 ms |
24832 KB |
sample_01.txt |
AC |
3 ms |
10496 KB |
sample_02.txt |
AC |
3 ms |
10496 KB |
sample_03.txt |
AC |
3 ms |
10496 KB |
sample_04.txt |
AC |
3 ms |
10496 KB |
x_01.txt |
AC |
464 ms |
24832 KB |
x_02.txt |
AC |
462 ms |
24832 KB |
x_03.txt |
AC |
462 ms |
24832 KB |
x_04.txt |
AC |
468 ms |
24832 KB |