Submission #21501414

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 2000000030;
constexpr ll INF= 2000000000000000001;
constexpr ll MOD = 1000000007;
const double PI = 3.14159265358979323846;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

template<typename T> 
vector<T> make_vector(size_t s) {
    return vector<T>(s);
}

template<typename T,typename... Args>
auto make_vector(size_t s,Args... args) {
    return vector(s,make_vector<T>(args...));
}

template<typename T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}

template<typename T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

ll mod(ll val, ll M) {
    val = val % M;
    if(val < 0) {
        val += M;
    }
    return val;
}

template<typename T>
T RS(T N, T P, T M){
    if(P == 0) {
        return 1;
    }
    if(P < 0) {
        return 0;
    }
    if(P % 2 == 0){
        ll t = RS(N, P/2, M);
        if(M == -1) return t * t;
        return t * t % M;
    }
    if(M == -1) {
        return N * RS(N,P - 1,M);
    }
    return N * RS(N, P-1, M) % M;
}

int main() {
    ll L;
    int N;
    cin >> L >> N;
    vector<ll> A;
    vector<ll> B;
    ll Sum = 0;
    for(int i = 0;i < N;i++) {
        ll x,y;
        cin >> x >> y;
        A.push_back(x + y - (L - 1));
        B.push_back(x - y);
    }
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    A.erase(unique(A.begin(),A.end()),A.end());
    B.erase(unique(B.begin(),B.end()),B.end());
    for(auto x:A) {
        Sum += L - abs(x);
    }
    for(auto x:B) {
        Sum += L - abs(x);
    }
    vector<ll> B0;
    vector<ll> B1;
    for(auto x:B) {
        if(x % 2 == 0) B0.push_back(x);
        else B1.push_back(x);
    }
    for(auto x:A) {
        int cnt = L - 1 - abs(x);
        if(cnt % 2 == 0) {
            auto itr = lower_bound(B0.begin(),B0.end(),-cnt);
            auto itr2 = upper_bound(B0.begin(),B0.end(),cnt);
            Sum -= distance(itr,itr2);
        }
        else {
            auto itr = lower_bound(B1.begin(),B1.end(),-cnt);
            auto itr2 = upper_bound(B1.begin(),B1.end(),cnt);
            Sum -= distance(itr,itr2);
        }
    }
    cout << Sum << endl;
}

Submission Info

Judge Result