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

• 問題: No.953 席
• ユーザー: %20
• 提出日時: 2018-08-09 23:28:09
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,490 bytes
• コンパイル時間: 2,183 ms
• コンパイル使用メモリ: 207,736 KB
• 実行使用メモリ: 6,016 KB
• 最終ジャッジ日時: 2024-07-01 03:42:55
• 合計ジャッジ時間: 9,877 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 ms; 5,248 KB
testcase_01	AC	4 ms; 5,376 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	AC	133 ms; 5,760 KB
testcase_08	AC	197 ms; 5,888 KB
testcase_09	AC	109 ms; 5,632 KB
testcase_10	AC	46 ms; 5,376 KB
testcase_11	AC	147 ms; 5,376 KB
testcase_12	WA	-
testcase_13	AC	204 ms; 5,888 KB
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	AC	205 ms; 5,888 KB
testcase_26	WA	-

コンパイルメッセージ

main.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main(){cin.tie(0);ios::sync_with_stdio(false);
      | ^~~~

ソースコード

#include<bits/stdc++.h>
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;
		}
	}
}