#775055 (C++23) No.1997 X Lighting

• 問題: No.1997 X Lighting
• ユーザー: hir355
• 提出日時: 2022-07-01 21:52:59
• 言語: C++23 (gcc 12.3.0 + boost 1.83.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	AC	5 ms; 5,248 KB
testcase_06	WA	-
testcase_07	AC	2 ms; 5,248 KB
testcase_08	WA	-
testcase_09	AC	3 ms; 5,248 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-

ソースコード

#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;
}