Submission #1387925
Source Code Expand
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
using namespace std;
const int maxn = 300010,inf = 1<<29;
int W,H,N,ans,tree[maxn*4],tag[maxn*4];
inline int gi()
{
char ch; int ret = 0,f = 1;
do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');
if (ch == '-') f = -1,ch = getchar();
do ret = ret*10+ch-'0',ch = getchar(); while (ch >= '0'&&ch <= '9');
return ret*f;
}
struct node
{
int x,y;
inline node(int _x = 0,int _y = 0):x(_x),y(_y) {}
inline void read() { x = gi(); y = gi(); }
friend inline bool operator <(const node &a,const node &b) { return a.x < b.x; }
}P[maxn];
inline void build(int now,int l,int r)
{
tree[now] = -inf; tag[now] = 0; if (l == r) return;
int mid = (l+r) >> 1;
build(now<<1,l,mid); build(now<<1|1,mid+1,r);
}
inline void pushdown(int now,int l,int r)
{
if (l != r)
{
tree[now<<1] += tag[now]; tag[now<<1] += tag[now];
tree[now<<1|1] += tag[now]; tag[now<<1|1] += tag[now];
}
tag[now] = 0;
}
inline void modify(int now,int l,int r,int ql,int qr,int key)
{
if (tag[now]) pushdown(now,l,r);
if (l == ql&&r == qr) { tree[now] += key; tag[now] = key; return; }
int mid = (l+r) >> 1;
if (qr <= mid) modify(now<<1,l,mid,ql,qr,key);
else if (ql > mid) modify(now<<1|1,mid+1,r,ql,qr,key);
else modify(now<<1,l,mid,ql,mid,key),modify(now<<1|1,mid+1,r,mid+1,qr,key);
tree[now] = max(tree[now<<1],tree[now<<1|1]);
}
inline void change(int now,int l,int r,int pos,int key)
{
if (tag[now]) pushdown(now,l,r);
if (l == r) { tree[now] = key; return; }
int mid = (l+r) >> 1;
if (pos <= mid) change(now<<1,l,mid,pos,key);
else change(now<<1|1,mid+1,r,pos,key);
tree[now] = max(tree[now<<1],tree[now<<1|1]);
}
inline void work()
{
sort(P+1,P+N+1); build(1,1,N+1);
stack <node> S1,S2; int mid = H>>1;
change(1,1,N+1,1,H); S1.push(node(mid,0)); S2.push(node(H-mid,0));
for (int i = 1;i <= N;++i)
{
ans = max(ans,(P[i].x+tree[1])<<1); int h;
if (P[i].y <= mid)
{
for (h = mid;!S1.empty()&&mid-P[i].y < (S1.top()).x;h = (S1.top()).x,S1.pop())
modify(1,1,N+1,(S1.top()).y+1,i,mid-P[i].y-h);
if (S1.empty()) S1.push(node(mid-P[i].y,0));
else modify(1,1,N+1,(S1.top()).y+1,i,mid-P[i].y-h);
S1.push(node(mid-P[i].y,i));
}
else
{
for (h = H-mid;!S2.empty()&&P[i].y-mid < (S2.top()).x;h = (S2.top()).x,S2.pop())
modify(1,1,N+1,(S2.top()).y+1,i,P[i].y-mid-h);
if (S2.empty()) S2.push(node(P[i].y-mid,0));
else modify(1,1,N+1,(S2.top()).y+1,i,P[i].y-mid-h);
S2.push(node(P[i].y-mid,i));
}
change(1,1,N+1,i+1,H-P[i].x);
}
ans = max(ans,(W+tree[1])<<1);
}
int main()
{
// freopen("D.in","r",stdin);
// freopen("D.out","w",stdout);
W = gi(); H = gi(); N = gi();
for (int i = 1;i <= N;++i) P[i].read();
ans = max((H+1)<<1,(W+1)<<1);
work();
for (int i = 1;i <= N;++i) swap(P[i].x,P[i].y); swap(H,W);
work();
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Pushing Balls |
User |
vjudge1 |
Language |
C++14 (Clang 3.8.0) |
Score |
0 |
Code Size |
2909 Byte |
Status |
WA |
Exec Time |
2103 ms |
Memory |
5888 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0.txt, example1.txt, example2.txt |
All |
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, example0.txt, example1.txt, example2.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
TLE |
2103 ms |
3840 KB |
001.txt |
TLE |
2103 ms |
3840 KB |
002.txt |
TLE |
2103 ms |
3840 KB |
003.txt |
TLE |
2103 ms |
3840 KB |
004.txt |
TLE |
2103 ms |
3840 KB |
005.txt |
TLE |
2103 ms |
3840 KB |
006.txt |
TLE |
2103 ms |
3840 KB |
007.txt |
TLE |
2103 ms |
3840 KB |
008.txt |
TLE |
2103 ms |
3840 KB |
009.txt |
TLE |
2103 ms |
3840 KB |
010.txt |
TLE |
2103 ms |
3840 KB |
011.txt |
TLE |
2103 ms |
3840 KB |
012.txt |
TLE |
2103 ms |
3840 KB |
013.txt |
TLE |
2103 ms |
3840 KB |
014.txt |
TLE |
2103 ms |
3840 KB |
015.txt |
TLE |
2103 ms |
3840 KB |
016.txt |
TLE |
2103 ms |
3840 KB |
017.txt |
TLE |
2103 ms |
3840 KB |
018.txt |
TLE |
2103 ms |
3840 KB |
019.txt |
TLE |
2103 ms |
3840 KB |
020.txt |
TLE |
2103 ms |
3840 KB |
021.txt |
TLE |
2103 ms |
3840 KB |
022.txt |
TLE |
2103 ms |
3840 KB |
023.txt |
TLE |
2103 ms |
3840 KB |
024.txt |
TLE |
2103 ms |
3840 KB |
025.txt |
TLE |
2103 ms |
3840 KB |
026.txt |
TLE |
2103 ms |
3840 KB |
027.txt |
TLE |
2103 ms |
3840 KB |
028.txt |
TLE |
2103 ms |
3840 KB |
029.txt |
TLE |
2103 ms |
3840 KB |
030.txt |
WA |
3 ms |
5888 KB |
031.txt |
TLE |
2103 ms |
3840 KB |
example0.txt |
TLE |
2103 ms |
3840 KB |
example1.txt |
WA |
3 ms |
5888 KB |
example2.txt |
TLE |
2103 ms |
3840 KB |