結果
問題 |
No.1997 X Lighting
|
ユーザー |
![]() |
提出日時 | 2022-07-01 22:12:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 2,733 bytes |
コンパイル時間 | 2,475 ms |
コンパイル使用メモリ | 207,700 KB |
最終ジャッジ日時 | 2025-01-30 02:55:59 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 1000000007; // constexpr int MOD = 998244353; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; int main() { ll n; int m; cin >> n >> m; // vector on(n, vector(n, 0)); vector<ll> diag1, diag2; while (m--) { ll y, x; cin >> y >> x; --y; --x; diag1.emplace_back(y + x); diag2.emplace_back(n - 1 - y + x); // for (int k : vector<int>{1, 3, 5, 7}) { // for (int r = y, c = x; 0 <= r && r < n && 0 <= c && c < n; r += DY8[k], c += DX8[k]) { // on[r][c] = true; // } // } } // REP(i, n) { // REP(j, n) cout << on[i][j]; // cout << '\n'; // } sort(ALL(diag1)); diag1.erase(unique(ALL(diag1)), diag1.end()); sort(ALL(diag2)); diag2.erase(unique(ALL(diag2)), diag2.end()); ll ans = 0; vector<pair<ll, ll>> seg; vector<ll> v[2]{{0, n * 2 - 2}, {}}; for (ll e : diag1) { ll l = n * 2 - 2, r = 0; if (e < n) { l = n - 1 - e; r = n * 2 - 2 - (n - 1 - e); } else { l = e - (n - 1); r = n * 2 - 2 - (e - (n - 1)); } ans += (r - l + 1 + 1) / 2; seg.emplace_back(l, r); v[l & 1].emplace_back(l); v[r & 1].emplace_back(r); } for (ll e : diag2) v[e & 1].emplace_back(e); int l[2]; REP(p, 2) { sort(ALL(v[p])); v[p].erase(unique(ALL(v[p])), v[p].end()); l[p] = v[p].size(); } vector<int> imos[2]{vector<int>(l[0], 0), vector<int>(l[1], 0)}; for (const auto [l, r] : seg) { const int le = lower_bound(ALL(v[l & 1]), l) - v[l & 1].begin(); const int ri = lower_bound(ALL(v[r & 1]), r) - v[r & 1].begin(); ++imos[l & 1][le]; if (ri + 1 < v[l & 1].size()) --imos[l & 1][ri + 1]; } REP(p, 2) FOR(i, 1, l[p]) imos[p][i] += imos[p][i - 1]; for (ll e : diag2) { if (e < n) { ans += n - (n - 1 - e); } else { ans += n - (e - (n - 1)); } ans -= imos[e & 1][lower_bound(ALL(v[e & 1]), e) - v[e & 1].begin()]; } cout << ans << '\n'; return 0; }