Description:

White Rabbit wants to know the maximum number of cars that can be put into to ensure that there is a way that allows all cars to perform their entire journey without damage.

(update: all cars should start at the edge of the square and go towards another side, cars which start at the corner can choose either of the two directions)

For example, in a 5*5 square

legal

illegal(These two cars will collide at (4,4))

illegal (One car will go into a damaged grid)

Input:

The first line of input contains two integers n and m(n <= 100000,m <= 100000)
For the next m lines,each line contains two integers x,y(1 <= x,y <= n), denoting the grid which is damaged by White Cloud.

Output:

Print a number,denoting the maximum number of cars White Rabbit can put into.

Sample Input:

2 0

Sample Output:

4

Hint:

题目链接

根据样例提示可知若没有damage的点则可以放 2 n ( n % 2 ) 2n-(n \% 2) 2n(n%2)(若n为奇数则中间行和中间列只能放一辆车)辆车,最后再判断damage点减一下就是答案。

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}

bool s1[maxn], s2[maxn];

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n, m;
	read(n); read(m);
	int ans = n * 2;
	mem(s1, 0);
	mem(s2, 0);
	for (int i = 0, x, y; i < m; ++i) {
		read(x); read(y);
		if (!s1[x]) {
			s1[x] = 1;
			ans--;
		}
		if (!s2[y]) {
			s2[y] = 1;
			ans--;
		}
	}
	if (n % 2 && !s1[n / 2 + 1] && !s2[n / 2 + 1]) {
		ans--;
	}
	printf("%d\n", ans);
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}