Submission #1371798
Source Code Expand
#define ONLINE_JUDGE
#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
#include<cstring>
#define HEAP priority_queue
#define rep(i, n) for(int i = 0, _end_ = (n); i < _end_; ++i)
#define per(i, n) for(int i = (n) - 1; i >= 0 ; --i)
#define forn(i, l, r) for(int i = (l), _end_ = (r); i <= _end_; ++i)
#define nrof(i, r, l) for(int i = (r), _end_ = (l); i >= _end_; --i)
#define FOR(a, b) for(auto (a): (b))
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define X first
#define Y second
#define eps 1e-6
#define pi 3.1415926535897932384626433832795
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(), x.end()
#define FILL(a, b) memset((a), (b), sizeof((a)))
#define MCPY(a, b) memcpy((a), (b), sizeof((b)))
using namespace std;
typedef long long LL;
typedef double flt;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef pair<int,int> pii;
typedef pair<int,LL> pil;
typedef pair<LL,int> pli;
typedef pair<LL,LL> pll;
typedef vector<pil> vil;
typedef vector<pii> vii;
typedef vector<pli> vli;
typedef vector<pll> vll;
const int iinf = 1e9 + 7;
const int oo = 0x3f3f3f3f;
const LL linf = 1ll << 60;
const flt dinf = 1e60;
template <typename T>
inline void scf(T &x)
{
bool f = 0; x = 0; char c = getchar();
while((c < '0' || c > '9') && c != '-') c = getchar();
if(c == '-') { f = 1; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
if(f) x = -x; return;
}
template <typename T1, typename T2>
void scf(T1 &x, T2 &y) { scf(x); return scf(y); }
template <typename T1, typename T2, typename T3>
void scf(T1 &x, T2 &y, T3 &z) { scf(x); scf(y); return scf(z); }
template <typename T1, typename T2, typename T3, typename T4>
void scf(T1 &x, T2 &y, T3 &z, T4 &w) { scf(x); scf(y); scf(z); return scf(w); }
inline char mygetchar(){ char c = getchar(); while(c == ' ' || c == '\n') c = getchar(); return c; }
template <typename T> inline bool chkmax(T &x, const T &y){ return y > x ? x = y, 1 : 0; }
template <typename T> inline bool chkmin(T &x, const T &y){ return y < x ? x = y, 1 : 0; }
#ifdef ONLINE_JUDGE
#define debug(...) ;
#else
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define DEBUG
#endif
//---------------------------------------------------------head----------------------------------------------------
const int maxn = 3e5 + 100;
struct point
{
int x, y;
point(int x = 0, int y = 0): x(x), y(y){}
}pnt[maxn];
int M, W, H, n, ans, hsh[maxn], h_n;
namespace seg
{
struct node
{
node *ch[2];
int num, tag;
node(int x = -iinf): num(x){ memset(ch, 0, sizeof ch); tag = 0; }
void push()
{
if(tag)
{
rep(i, 2) ch[i]->tag += tag, ch[i]->num += tag;
tag = 0;
}
return;
}
void pull()
{
num = -iinf;
rep(i, 2) chkmax(num, ch[i]->num);
return;
}
}*root;
int seg_a, seg_b, seg_q, n;
void B(node* &u, int l, int r)
{
u = new node;
if(l == r)
{
u->num = -hsh[l];
return;
}
int mid = l + r >> 1;
B(u->ch[0], l, mid);
B(u->ch[1], mid + 1, r);
return u->pull();
}
void B(int _n)
{
root = 0; n = _n;
B(root, 0, n - 1);
return;
}
void Q(node* &u, int l, int r)
{
if(seg_a <= l && r <= seg_b)
{
chkmax(seg_q, u->num);
return;
}
int mid = l + r >> 1; u->push();
if(seg_a <= mid) Q(u->ch[0], l, mid);
if(mid < seg_b) Q(u->ch[1], mid + 1, r);
return;
}
int Q(int l, int r)
{
if(l > r) return -iinf;
seg_a = l, seg_b = r, seg_q = -iinf;
Q(root, 0, n - 1);
return seg_q;
}
void M(node* &u, int l, int r)
{
if(seg_a <= l && r <= seg_b)
{
u->num += seg_q;
u->tag += seg_q;
return;
}
int mid = l + r >> 1; u->push();
if(seg_a <= mid) M(u->ch[0], l, mid);
if(mid < seg_b) M(u->ch[1], mid + 1, r);
return u->pull();
}
void M(int l, int r, int x)
{
if(l > r) return;
//debug("M(%d, %d, %d)\n", l, r, x);
seg_a = l, seg_b = r, seg_q = x;
return M(root, 0, n - 1);
}
}
struct stk
{
struct item
{
int x, y, i;
item(int x = 0, int y = 0, int i = 0): x(x), y(y), i(i){}
}num[maxn];
int n;
stk(){ n = 0; }
void push(int x, int y)
{
int i = lower_bound(hsh, hsh + h_n, y) - hsh;
//debug("push(%d, %d)\t%d\n", x, y, i);
if(!n)
{
num[n++] = item(x, y, i);
return;
}
seg::M(num[n - 1].i, i - 1, x);
while(n && num[n - 1].x > x)
{
--n;
seg::M(n ? num[n - 1].i : 0, num[n].i - 1, x - num[n].x);
}
num[n++] = item(x, y, i);
return;
}
void upd(int i, int x)
{
int j = n ? num[n - 1].i : 0;
debug("\tupd(%d %d, %d)\n", j, i, x);
seg::M(j, i, x);
return;
}
void undo(int i, int x)
{
int j = n ? num[n - 1].i : 0;
seg::M(j, i, -x);
return;
}
}*A, *B;
void work()
{
M = W >> 1; h_n = 0;
sort(pnt, pnt + n, [&](point a, point b){ return a.y < b.y; });
rep(i, n) hsh[h_n++] = pnt[i].y;
h_n = unique(hsh, hsh + h_n) - hsh;
#ifdef DEBUG
rep(i, n) printf("%d %d\n", pnt[i].x, pnt[i].y);
debug("%d\n", M);
rep(i, h_n) printf("%d ", hsh[i]); putchar('\n');
#endif
seg::B(h_n);
A = new stk; B = new stk;
for(int i = -1, j = 0, y = hsh[j]; j < h_n ; y = hsh[++j])
{
debug("===============================================================\n%d\n", y);
while(i + 1 < n && pnt[i + 1].y == y)
{
++i;
if(pnt[i].x <= M) A->push(-pnt[i].x, pnt[i].y);
else B->push(pnt[i].x, pnt[i].y);
}
A->upd(min(j + 1, h_n - 1), 0); B->upd(min(j + 1, h_n - 1), W);
chkmax(ans, seg::Q(0, j) + ((j == h_n - 1) ? H : hsh[j + 1]));
A->undo(min(j + 1, h_n - 1), 0); B->undo(min(j + 1, h_n - 1), W);
debug("%d\n", ans);
}
return;
}
int main()
{
scf(W, H, n);
for(int i = 0; i < n; ++i)
{
int x, y; scf(x, y);
if(!x || !y){ --i, --n; continue; }
pnt[i] = point(x, y);
}
pnt[n++] = point(0, 0);
pnt[n++] = point(W, 0);
pnt[n++] = point(0, H);
pnt[n++] = point(W, H);
work();
swap(W, H);
rep(i, n) swap(pnt[i].x, pnt[i].y);
work();
printf("%d\n", ans << 1);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Snuke's Coloring 2 |
User |
King_George |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
6167 Byte |
Status |
AC |
Exec Time |
863 ms |
Memory |
55296 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 |
842 ms |
55296 KB |
dia_02.txt |
AC |
841 ms |
55296 KB |
dia_03.txt |
AC |
841 ms |
55296 KB |
dia_04.txt |
AC |
847 ms |
55296 KB |
dial_01.txt |
AC |
828 ms |
55296 KB |
dial_02.txt |
AC |
840 ms |
55296 KB |
dial_03.txt |
AC |
844 ms |
55296 KB |
dial_04.txt |
AC |
844 ms |
55296 KB |
dial_05.txt |
AC |
837 ms |
55296 KB |
dial_06.txt |
AC |
839 ms |
55296 KB |
dialr_01.txt |
AC |
826 ms |
55296 KB |
dialr_02.txt |
AC |
828 ms |
55296 KB |
dialr_03.txt |
AC |
826 ms |
55296 KB |
dialr_04.txt |
AC |
828 ms |
55296 KB |
diar_01.txt |
AC |
852 ms |
55296 KB |
diar_02.txt |
AC |
856 ms |
55296 KB |
diar_03.txt |
AC |
858 ms |
55296 KB |
hand_01.txt |
AC |
8 ms |
16640 KB |
hand_02.txt |
AC |
9 ms |
16640 KB |
hand_03.txt |
AC |
8 ms |
16640 KB |
hand_04.txt |
AC |
8 ms |
16640 KB |
hand_05.txt |
AC |
8 ms |
16640 KB |
poc_t_1.txt |
AC |
8 ms |
16640 KB |
poc_t_2.txt |
AC |
9 ms |
16640 KB |
poc_t_3.txt |
AC |
8 ms |
16640 KB |
poc_t_4.txt |
AC |
8 ms |
16640 KB |
poc_t_5.txt |
AC |
8 ms |
16640 KB |
poc_w_1.txt |
AC |
8 ms |
16640 KB |
poc_w_2.txt |
AC |
8 ms |
16640 KB |
random0_01.txt |
AC |
839 ms |
55296 KB |
random0_02.txt |
AC |
829 ms |
55296 KB |
random0_03.txt |
AC |
851 ms |
55296 KB |
random1_01.txt |
AC |
830 ms |
55296 KB |
random1_02.txt |
AC |
829 ms |
55296 KB |
random1_03.txt |
AC |
833 ms |
55296 KB |
random1_04.txt |
AC |
834 ms |
55296 KB |
random1_05.txt |
AC |
836 ms |
55296 KB |
random1_06.txt |
AC |
832 ms |
55296 KB |
random1_07.txt |
AC |
829 ms |
55296 KB |
rect_01.txt |
AC |
827 ms |
55296 KB |
rect_02.txt |
AC |
829 ms |
55296 KB |
rect_03.txt |
AC |
829 ms |
55296 KB |
rect_04.txt |
AC |
863 ms |
55296 KB |
rect_05.txt |
AC |
825 ms |
55296 KB |
rect_06.txt |
AC |
837 ms |
55296 KB |
rect_07.txt |
AC |
829 ms |
55296 KB |
rect_08.txt |
AC |
830 ms |
55296 KB |
rect_09.txt |
AC |
829 ms |
55296 KB |
rect_10.txt |
AC |
828 ms |
55296 KB |
sample_01.txt |
AC |
8 ms |
16640 KB |
sample_02.txt |
AC |
8 ms |
16640 KB |
sample_03.txt |
AC |
8 ms |
16640 KB |
sample_04.txt |
AC |
8 ms |
16640 KB |
x_01.txt |
AC |
743 ms |
55296 KB |
x_02.txt |
AC |
739 ms |
55296 KB |
x_03.txt |
AC |
737 ms |
55296 KB |
x_04.txt |
AC |
742 ms |
55296 KB |