結果

問題 No.1997 X Lighting
ユーザー ruthen71
提出日時 2022-07-01 22:50:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 57 ms / 2,000 ms
コード長 1,651 bytes
コンパイル時間 2,178 ms
コンパイル使用メモリ 201,852 KB
最終ジャッジ日時 2025-01-30 03:20:04
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#ifdef _RUTHEN
#include "debug.hpp"
#else
#define show(...) true
#endif
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll N, M;
cin >> N >> M;
show(N, M);
V<ll> x(M), y(M);
rep(i, M) {
cin >> x[i] >> y[i];
x[i]--, y[i]--;
}
show(x, y);
V<ll> z(M);
rep(i, M) z[i] = x[i] + y[i];
sort(z.begin(), z.end());
z.erase(unique(z.begin(), z.end()), z.end());
show(z);
ll ans = 0;
V<ll> ze, zo;
for (auto zi : z) {
// x+y=k
if (zi < N) {
ans += zi + 1;
} else {
ans += 2 * N - 1 - zi;
}
if (zi % 2 == 1) {
zo.push_back(zi);
} else {
ze.push_back(zi);
}
}
show(ans);
V<ll> w(M);
rep(i, M) w[i] = y[i] - x[i];
sort(w.begin(), w.end());
w.erase(unique(w.begin(), w.end()), w.end());
for (auto wi : w) {
wi = abs(wi);
ans += N - wi;
if (wi % 2 == 1) {
// zo
int ind1 = lower_bound(zo.begin(), zo.end(), wi) - zo.begin();
int ind2 = upper_bound(zo.begin(), zo.end(), 2 * (N - 1) - wi) - zo.begin();
ans -= ind2 - ind1;
} else {
// ze
int ind1 = lower_bound(ze.begin(), ze.end(), wi) - ze.begin();
int ind2 = upper_bound(ze.begin(), ze.end(), 2 * (N - 1) - wi) - ze.begin();
ans -= ind2 - ind1;
}
}
cout << ans << '\n';
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0