Submission #1230837

---

Source Code Expand

#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <string>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define REP(i, x, y) for(int i = (int)x; i <= (int)y; i ++)
#define FOR(i, x, y) for(int i = (int)x; i <  (int)y; i ++)
#define PER(i, x, y) for(int i = (int)x; i >= (int)y; i --)
#define trace(x) cerr << #x << " " << x << endl;
#define dprintf(...) fprintf(stderr, __VA__ARGS__)
#define dln()        fprintf(stderr, "\n")
using namespace std;
typedef long long LL;
typedef long double db;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
const	int N = 300005;
const	int P = 1e9 + 7;
const	int inf = 1e9;
const	LL Inf = 1e15;
 
inline int IN(){
	char ch = getchar(); int x = 0, f = 0;
	while(ch < '0' || ch > '9') ch = getchar(), f = (ch == '-');
	while(ch >= '0' && ch <= '9'){
		x = (x << 1) + (x << 3) + ch - 48;
		ch = getchar();
	}
	return f ? (-x) : x;
}
 
inline int Pow(int x, int y, int p){
	int an = 1;
	for(; y; y >>= 1, x = (LL)x * x % p) if(y & 1) an = (LL)an * x % p;
	return an;
}
 
void renew(int &x, int y){
	x += y;
	if(x < 0) x += P;
	else if(x >= P) x -= P;
}
 
template<typename T> inline void chkmin(T &a, const T &b) {if(a > b) a = b;}
template<typename T> inline void chkmax(T &a, const T &b) {if(a < b) a = b;}
 
int W, H, ans, n;
struct node{
	int x, y;
}a[N], b[N], c[N];
int Y[N], ytot;
 
namespace Tree{
	int Add[N << 2], Max[N << 2];
	
	#define md     (((L) + (R)) >> 1)
	#define ls     ((x) << 1)
	#define rs     ((ls) | 1)
 
	void upd(int x){
		Max[x] = max(Max[x << 1], Max[(x << 1) | 1]);
	}
 
	void tag(int x, int v){
		Add[x] += v;
		Max[x] += v;
	}
 
	void sep(int x){
		tag(x << 1, Add[x]);
		tag((x << 1) | 1, Add[x]);
		Add[x] = 0;
	}
 
	void Bud(int x, int L, int R){
		Add[x] = 0;
		if(L == R){
			Max[x] = -Y[L] * 2;
			return;
		}
		Bud(ls, L, md);
		Bud(rs, md + 1, R);
		upd(x);	
	}
	
	int ql, qr, qv;
	void A(int x, int L, int R){
		if(ql <= L && R <= qr){
			tag(x, qv);
			return;
		}
		sep(x);
		if(ql <= md) A(ls, L, md);
		if(md <  qr) A(rs, md + 1, R);
		upd(x);
	}
 
	int Q(int x, int L, int R){
		if(ql <= L && R <= qr) return Max[x];
		sep(x);
		int res = -inf;
		if(ql <= md) chkmax(res, Q(ls, L, md));
		if(md <  qr) chkmax(res, Q(rs, md + 1, R));
		return res;
	}
 
	void init(int ytot){
		Bud(1, 1, ytot);
	}	
}
 
int STA[N], Atot, atot;
int STB[N], Btot, btot;
 
void work(int mid){
	ytot = atot = btot = Atot = Btot = 0;
	REP(i, 1, n){
		if(!a[i].y) continue;
		if(a[i].x <= mid){
			b[++atot] = (node){a[i].y, ((mid - a[i].x) << 1) + 1};
		}else{
			c[++btot] = (node){a[i].y, ((a[i].x - mid) << 1) - 1};
		}
		Y[++ytot] = a[i].y;
	}
	Y[++ytot] = H;
	Y[++ytot] = 0;
	sort(Y + 1, Y + ytot + 1); 
	ytot = unique(Y + 1, Y + ytot + 1) - (Y + 1);
	REP(i, 1, atot) b[i].x = lower_bound(Y + 1, Y + ytot + 1, b[i].x) - Y;
	REP(i, 1, btot) c[i].x = lower_bound(Y + 1, Y + ytot + 1, c[i].x) - Y;
	sort(b + 1, b + atot + 1, [&](const node &a, const node &b){if(a.x == b.x) return a.y > b.y;return a.x < b.x;});
	sort(c + 1, c + btot + 1, [&](const node &a, const node &b){if(a.x == b.x) return a.y > b.y;return a.x < b.x;});
	Tree :: init(ytot);
	int x = 1, y = 1;
	STA[Atot = 1] = 0; STB[Btot = 1] = 0;
	b[0].x = b[0].y = 0; b[0].x = 1;
	c[0].x = c[0].y = 0; c[0].x = 1;
	//using namespace Tree;
	Tree :: ql = 1, Tree :: qr = ytot, Tree :: qv = W << 1;
	//printf("Add %d %d %d\n", ql, qr, qv);
	Tree :: A(1, 1, ytot);
	REP(i, 1, ytot){
		Tree :: ql = 1, Tree :: qr = i - 1;
		if(i >= 2) chkmax(ans, Tree :: Q(1, 1, ytot) + Y[i] * 2);
		for(; x <= atot && b[x].x == i; x ++) {
			Tree :: ql = b[STA[Atot]].x, Tree :: qr = ytot, Tree :: qv = -(mid * 2 + 1), Tree :: A(1, 1, ytot);
			while(Atot && b[STA[Atot]].y >= b[x].y){
				Tree :: qr = b[STA[Atot]].x - 1; 
				Tree :: ql = b[STA[Atot - 1]].x;
				Tree :: qv = -b[STA[Atot]].y;
				//printf("Add %d %d %d\n", ql, qr, qv);
				Tree :: A(1, 1, ytot);
				--Atot;
			}
			++Atot; STA[Atot] = x;
			Tree :: qr = b[STA[Atot]].x - 1, Tree :: ql = b[STA[Atot - 1]].x, Tree :: qv = b[STA[Atot]].y, Tree :: A(1, 1, ytot);
			Tree :: ql = b[STA[Atot]].x, Tree :: qr = ytot, Tree :: qv = mid * 2 + 1, Tree :: A(1, 1, ytot);
			//printf("Add %d %d %d\n", ql, qr, qv);
		}
		for(; y <= btot && c[y].x == i; y ++) {
			Tree :: ql = c[STB[Btot]].x, Tree :: qr = ytot, Tree :: qv = -((W - mid) * 2 - 1), Tree :: A(1, 1, ytot);
			while(Btot && c[STB[Btot]].y >= c[y].y){
				Tree :: qr = c[STB[Btot]].x - 1; 
				Tree :: ql = c[STB[Btot - 1]].x;
				Tree :: qv = -c[STB[Btot]].y;
				//printf("Add %d %d %d\n", ql, qr, qv);
				Tree :: A(1, 1, ytot);
				--Btot;
			}
			++Btot; STB[Btot] = y;
			Tree :: qr = c[STB[Btot]].x - 1, Tree :: ql = c[STB[Btot - 1]].x, Tree :: qv = c[STB[Btot]].y, Tree :: A(1, 1, ytot);
			Tree :: ql = c[STB[Btot]].x, Tree :: qr = ytot, Tree :: qv = ((W - mid) << 1) - 1, Tree :: A(1, 1, ytot);
		}
	
	}
}
 
int main(){
	scanf("%d%d%d", &W, &H, &n);
	if(min(W, H) == 1 || n == 0){
		printf("%d\n", 2 * (W + H));
		return 0;
	}
	ans = max(W, H) * 2 + 2;
	REP(i, 1, n) scanf("%d%d", &a[i].x, &a[i].y);
	work(W >> 1);
	swap(W, H); REP(i, 1, n) swap(a[i].x, a[i].y);
	work(W >> 1);
	printf("%d\n", ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:197: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:203:46: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  REP(i, 1, n) scanf("%d%d", &a[i].x, &a[i].y);
                                              ^

Judge Result