結果

問題 No.1997 X Lighting
ユーザー hir355hir355
提出日時 2022-07-01 21:52:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,623 bytes
コンパイル時間 3,658 ms
コンパイル使用メモリ 258,056 KB
実行使用メモリ 14,464 KB
最終ジャッジ日時 2024-11-26 04:46:20
合計ジャッジ時間 6,456 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 3 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = int64_t;
using graph = vector<vector<ll>>;

int main() {
	ll l,n;
	cin >> l >> n;
	set<ll> s1,s2,s3,s4;
	ll ans=0;
	for(ll i=0;i<n;i++){
		ll x,y;
		cin >> x >> y;
		if((x+y)%2==0){
			s1.insert(x+y);
			s2.insert(x-y);
		}else{
			s3.insert(x+y);
			s4.insert(x-y);
		}
	}
	ll k1=s1.size();
	ll k2=s2.size();
	ll k3=s3.size();
	ll k4=s4.size();
	auto itr=s1.begin();
	for(ll i=0;i<k1;i++){
		ans+=l-abs(*itr-l+1);
		itr++;
	}
	itr=s2.begin();
	for(ll i=0;i<k2;i++){
		ans+=l-abs(*itr);
		itr++;
	}
	itr=s3.begin();
	for(ll i=0;i<k3;i++){
		ans+=l-abs((*itr)-l+1);
		itr++;
	}
	itr=s4.begin();
	for(ll i=0;i<k4;i++){
		ans+=l-abs(*itr);
		itr++;
	}
	ll a1[k1],a2[k2],a3[k3],a4[k4];
	itr=s1.begin();
	for(ll i=0;i<k1;i++) a1[i]=min(*itr,(l-1)*2-*itr),itr++;
	itr=s2.begin();
	for(ll i=0;i<k2;i++) a2[i]=abs(*itr),itr++;
	itr=s3.begin();
	for(ll i=0;i<k3;i++) a3[i]=min(*itr,(l-1)*2-*itr),itr++;
	itr=s4.begin();
	for(ll i=0;i<k4;i++) a4[i]=abs(*itr),itr++;
	sort(a1,a1+k1);
	sort(a2,a2+k2);
	sort(a3,a3+k3);
	sort(a4,a4+k4);
	for(ll i=0;i<k2;i++){
		if(a1[0]>=a2[i]){
        	ans-=k1;
          	continue;
        }  
		ll ng=0,ok=k1;
		while(ok-ng>1){
			ll k=(ok+ng)/2;
			if(a1[k]>=a2[i]) ok=k;
			else ng=k;
		}
		ans-=k1-ok;
	}
	for(ll i=0;i<k4;i++){
		if(a3[0]>=a4[i]){
          	ans-=k3;
      		continue;
        }  
		ll ng=0,ok=k3;
		while(ok-ng>1){
			ll k=(ok+ng)/2;
			if(a3[k]>=a4[i]) ok=k;
			else ng=k;
		}
		ans-=k3-ok;
	}
	cout << ans << endl;
	return 0;
}
0