#408514 (C++17) No.953 席

• 問題: No.953 席
• ユーザー: %20
• 提出日時: 2019-12-14 16:37:58
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 1,512 bytes
• コンパイル時間: 2,094 ms
• コンパイル使用メモリ: 207,764 KB
• 実行使用メモリ: 9,984 KB
• 最終ジャッジ日時: 2023-09-15 15:25:43
• 合計ジャッジ時間: 8,865 ms
• ジャッジサーバーID （参考情報）: judge12 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 ms; 7,568 KB
testcase_01	AC	4 ms; 7,740 KB
testcase_02	AC	191 ms; 9,152 KB
testcase_03	AC	189 ms; 9,012 KB
testcase_04	AC	190 ms; 8,968 KB
testcase_05	AC	185 ms; 8,808 KB
testcase_06	AC	190 ms; 8,964 KB
testcase_07	AC	139 ms; 8,668 KB
testcase_08	AC	202 ms; 9,600 KB
testcase_09	AC	113 ms; 8,784 KB
testcase_10	AC	47 ms; 7,792 KB
testcase_11	AC	151 ms; 8,796 KB
testcase_12	AC	204 ms; 9,308 KB
testcase_13	AC	213 ms; 9,680 KB
testcase_14	AC	202 ms; 9,628 KB
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	AC	193 ms; 9,152 KB
testcase_24	WA	-
testcase_25	AC	214 ms; 9,696 KB
testcase_26	AC	178 ms; 8,716 KB

コンパイルメッセージ

main.cpp:73:1: 警告: ISO C++ では型の無い ‘main’ の宣言を禁止しています [-Wreturn-type]
   73 | main(){cin.tie(0);ios::sync_with_stdio(false);
      | ^~~~

ソースコード

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int>pii;

const int S=1<<17;
pii s[2*S];
int N,K1,K2;

int cmp(int a,int b){
	if(a==0)return b;
	if(b==0)return a;
	if(2*abs(a-K1)+abs(a-K2)<2*abs(b-K1)+abs(b-K2)){
		return a;
	}else{
		return b;
	}
}

pii op(pii a,pii b){
	return pii{cmp(a.first,b.first),cmp(a.second,b.second)};
}

pii init(int i){
	if(i<S){
		s[i]=op(init(i*2),init(i*2+1));
	}else if(S+1<=i&&i<=S+N){
		s[i]={S^i,S^i};
	}
	return s[i];
}

void update(int i,int a,int b){
	if(b>=0){
		s[S|i]={a,b};
	}else{
		s[S|i].first=a;
	}
	for(i|=S;i/2>=1;i/=2){
		s[i/2]=op(s[i],s[i^1]);
	}
}

void sitdown(int i){
	cout<<i<<endl;
	update(i,0,0);
	if(i>1){
		update(i-1,0,-1);
	}
	if(i<N){
		update(i+1,0,-1);
	}
}

void standup(int i){
	if((i==1||s[S|i-1].second)&&(i==N||s[S|i+1].second)){
		update(i,i,i);
	}else{
		update(i,0,i);
	}
	if(i>1){
		if(s[S|i-1].second&&(i-1==1||s[S|i-2].second)){
			update(i-1,i-1,i-1);
		}
	}
	if(i<N){
		if(s[S|i+1].second&&(i+1==N||s[S|i+2].second)){
			update(i+1,i+1,i+1);
		}
	}
}

main(){cin.tie(0);ios::sync_with_stdio(false);
	cin>>N>>K1>>K2;
	init(1);
	int Q;
	cin>>Q;
	vector<int>a(Q),b(Q);
	for(int i=0;i<Q;++i){
		cin>>a[i]>>b[i];
	}
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	for(int i=0;i<Q;){
		while(pq.size()&&pq.top().first<=a[i]){
			standup(pq.top().second);
			pq.pop();
		}
		if(int x=s[1].first?:s[1].second){
			pq.push({a[i]+b[i],x});
			sitdown(x);
			++i;
		}else{
			a[i]=pq.top().first;
		}
	}
}