結果

問題 No.1997 X Lighting
ユーザー EnderedEndered
提出日時 2022-07-20 21:43:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 389 ms / 2,000 ms
コード長 6,269 bytes
コンパイル時間 1,913 ms
コンパイル使用メモリ 185,316 KB
実行使用メモリ 18,908 KB
最終ジャッジ日時 2023-09-15 10:16:58
合計ジャッジ時間 7,870 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 4 ms
4,380 KB
testcase_06 AC 21 ms
4,564 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 4 ms
4,376 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 1 ms
4,384 KB
testcase_13 AC 36 ms
5,884 KB
testcase_14 AC 230 ms
18,908 KB
testcase_15 AC 63 ms
7,332 KB
testcase_16 AC 91 ms
8,628 KB
testcase_17 AC 279 ms
15,764 KB
testcase_18 AC 124 ms
10,188 KB
testcase_19 AC 349 ms
18,196 KB
testcase_20 AC 385 ms
18,844 KB
testcase_21 AC 389 ms
18,592 KB
testcase_22 AC 347 ms
18,128 KB
testcase_23 AC 154 ms
11,416 KB
testcase_24 AC 5 ms
4,376 KB
testcase_25 AC 365 ms
18,096 KB
testcase_26 AC 292 ms
15,876 KB
testcase_27 AC 321 ms
16,184 KB
testcase_28 AC 72 ms
7,668 KB
testcase_29 AC 67 ms
7,500 KB
testcase_30 AC 384 ms
17,928 KB
testcase_31 AC 213 ms
13,244 KB
testcase_32 AC 39 ms
5,920 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,a,...) for(int i = (a)*(strlen(#__VA_ARGS__)!=0);i<(int)(strlen(#__VA_ARGS__)?__VA_ARGS__:(a));++i)
#define per(i,a,...) for(int i = (strlen(#__VA_ARGS__)?__VA_ARGS__:(a))-1;i>=(int)(strlen(#__VA_ARGS__)?(a):0);--i)
#define foreach(i, n) for(auto &i:(n))
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
#define lambda(RES_TYPE, ...) (function<RES_TYPE(__VA_ARGS__)>)[&](__VA_ARGS__) -> RES_TYPE
#define method(FUNC_NAME, RES_TYPE, ...) function<RES_TYPE(__VA_ARGS__)> FUNC_NAME = lambda(RES_TYPE, __VA_ARGS__)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define debug(x) cout<<"LINE "<<__LINE__<<": "<<#x<<" = "<<x<<endl;
#else
#define debug(x) (void)0
#endif

namespace templates{
    ll modpow(ll x, ll b,ll mod=MOD){
        ll res = 1;
        while(b){
            if(b&1)res = res * x % mod;
            x = x * x % mod;
            b>>=1;
        }
        return res;
    }

    ll modinv(ll x){
        return modpow(x, MOD-2);
    }

    bool was_output = false;

    void print();
    template <class t> void print(const vector<t> &);
    template <class t, class u> void print(const pair<t, u> &);
    template <class t> void print(const t&);
    template <class Head, class... Tail> void print(const Head&, const Tail&...);

    template <class t> void println(const vector<vector<t>>&);
    template <class t> void println(const vector<t>&);
    template <class t> void println(const t&);
    template <class Head, class... Tail> void println(const Head&, const Tail&...);
    void println();
    void newline();

    void print(){
        return;
    }

    template <class t>
    void print(const vector<t>&x){
        for(const t&i:x)print(i);
    }
    template <class t, class u>
    void print(const pair<t,u>&p){
        print(p.first);
        print(p.second);
    }
    template <class t>
    void print(const t&x){
        if(was_output)cout<<" ";
        cout<<x;
        was_output = true;
    }
    template <class Head, class... Tail>
    void print(const Head&head,const Tail&...tail){
        print(head);
        print(tail...);
    }

    template<class t>
    void println(const vector<vector<t>>&x){
        for(vector<t> i:x)println(i);
    }
    template<class t>
    void println(const vector<t>&x){
        for(const t&i:x)print(i);
        println();
    }
    template <class t>
    void println(const t&x){
        print(x);
        println();
    }
    void println(){
        if(was_output){
            cout << endl;
            was_output = false;
        }
    }
    template <class Head, class... Tail>
    void println(const Head&head,const Tail&...tail){
        print(head);
        println(tail...);
    }

    void newline(){
        was_output = true;
        println();
    }

    template<class t>
    istream& operator>>(istream&is, vector<t>&x){
        for(auto &i:x)is >> i;
        return is;
    }

    template<class t, class u>
    istream& operator>>(istream&is, pair<t, u>&x){
        is >> x.first >> x.second;
        return is;
    }

    template<class t>
    ostream& operator<<(ostream&os, vector<t> &v){
        os << "{";
        for(t &i:v){
            os << i << ", ";
        }
        os << "}";
        return os;
    }

    template<class t = long long>
    t in(){
        t res; cin >> res; return res;
    }

    template<class t>
    vector<t> sorted(vector<t> line,function<bool(t,t)> comp=[](t a,t b){return a<b;}){
        sort(line.begin(),line.end(),comp);
        return line;
    }

    template<class t>
    vector<t> reversed(vector<t> line){
        reverse(line.begin(),line.end());
        return line;
    }
    string reversed(string str){
        reverse(str.begin(),str.end());
        return str;
    }

    long long gcd(long long a,long long b){
        while(b){
            a %= b;
            swap(a,b);
        }
        return a;
    }

    long long lcm(long long a,long long b){
        return a / gcd(a,b) * b;
    }

    class output_initializer{
    public:
        output_initializer(){
            ios::sync_with_stdio(false);
            cin.tie(nullptr);
            cout << setprecision(20);
        }
    };output_initializer OUTPUT_INITIALIZER_INSTANCE = output_initializer();
}

using namespace templates;

ll func(){
    ll n = in();
    int m = in();
    method(calc,ll,vector<pll> line){
        ll res = 0;
        map<ll,ll> adds;
        set<ll> uy;
        set<ll> ux;
        foreach(i,line){
            ll y = i.first;
            ll x = i.second;
            if(ux.count(x-y)==0){
                res += min(n-x,n-y) - max(1-x,1-y) + 1;
                ++adds[abs(x-y)+1];
                --adds[2*n-abs(x-y)+1];
                ux.emplace(x-y);
            }
            if(uy.count(x+y)==0){
                res += min(n-x,y-1) - max(1-x,y-n) + 1;
                uy.emplace(x+y);
            }
        }
        int sum = 0;
        foreach(i,adds){
            sum += i.second;
            i.second = sum;
        }
        set<ll> used;
        foreach(i,line){
            ll y = i.first;
            ll x = i.second;
            ll p = y+x-1;
            if(used.count(p))continue;
            used.emplace(p);
            if(p>n)++p;
            auto itr = adds.upper_bound(p);
            if(itr==adds.begin())continue;
            --itr;
            res -= itr->second;
        }
        return res;
    };
    vector<pll> evens;
    vector<pll> odds;
    rep(i,m){
        ll y = in();
        ll x = in();
        if((y+x)%2){
            odds.emplace_back(y,x);
        }else{
            evens.emplace_back(y,x);
        }
    }
    return calc(evens) + calc(odds);
}

int main(){
    println(func());
    return 0;
}
0