結果
問題 | No.1997 X Lighting |
ユーザー |
![]() |
提出日時 | 2023-08-09 14:18:59 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 235 ms / 2,000 ms |
コード長 | 1,107 bytes |
コンパイル時間 | 5,891 ms |
コンパイル使用メモリ | 317,956 KB |
実行使用メモリ | 11,292 KB |
最終ジャッジ日時 | 2024-11-15 10:05:52 |
合計ジャッジ時間 | 10,419 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;using mint=modint998244353; //1000000007;using ll=long long;using pp=pair<ll,ll>;#define sr string#define vc vector#define fi first#define se second#define rep(i,n) for(int i=0;i<(int)n;i++)#define pb push_back#define all(v) v.begin(),v.end()#define pque priority_queue#define bpc(a) __builtin_popcount(a)int main(){ll n,m;cin>>n>>m;vc<pp>va,vb;rep(i,m){ll x,y;cin>>x>>y;if((x+y)&1)va.pb({x,y});else vb.pb({x,y});}ll res=0;auto f=[&](vc<pp>v)->void{set<ll>s,sx;for(auto [x,y]:v){ll t=x+y-1;s.insert(t);sx.insert(x-(y-1));}for(ll t:s){res+=t;if(t>n)res-=2*(t-n);}vc<ll>sv(1,0);for(ll t:s)sv.pb(t);for(ll t:sx){if(t<1)res+=n-(1-t);else res+=n+1-t;// 1<= (t+at)/2<=n at>=t (at-t)/2<=n-1 at<= 2n-2+tll l=max(2-t,t),r=min(2*n-2+t,2*n-t);ll it=upper_bound(all(sv),r)-lower_bound(all(sv),l);res-=it;}};f(va); f(vb);cout<<res;}