なかなかにめんどくさい。
#include<cstdio> #include <cstdlib> #include<queue> #include<set> #define rep(i,n) for(int i = 0; i < n; i++) using namespace std; typedef long long ll; int main(){ int l, n, inx, iny, z, c, j; ll ans = 0; set<int> sx, sy; set<int>::iterator it; priority_queue<int, vector<int>, greater<int> > x[2]; priority_queue<int> y[2]; scanf("%d%d",&l,&n); rep(i,n){ scanf("%d%d",&inx,&iny); sx.insert(inx+iny); sy.insert(inx-iny); } for(it = sx.begin(); it != sx.end(); it++){z = l-abs(*it - l + 1); x[z % 2].push(z); ans += z;} for(it = sy.begin(); it != sy.end(); it++){z = l-abs(*it); y[z % 2].push(z); ans += z;} rep(i,2){ c = 0; j = (i+l+1) % 2; while(!x[i].empty()){ while(!y[j].empty() && y[j].top() >= l+1-x[i].top()){y[j].pop(); c++;} ans -= c; x[i].pop(); } } printf("%lld\n",ans); return 0; }