#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,143 ms
• コンパイル使用メモリ: 208,756 KB
• 実行使用メモリ: 9,816 KB
• 最終ジャッジ日時: 2024-07-02 18:07:45
• 合計ジャッジ時間: 10,234 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	5 ms; 6,880 KB
testcase_01	AC	5 ms; 6,944 KB
testcase_02	AC	190 ms; 8,928 KB
testcase_03	AC	190 ms; 6,944 KB
testcase_04	AC	190 ms; 7,776 KB
testcase_05	AC	186 ms; 8,420 KB
testcase_06	AC	190 ms; 8,288 KB
testcase_07	AC	138 ms; 8,032 KB
testcase_08	AC	198 ms; 8,848 KB
testcase_09	AC	110 ms; 7,904 KB
testcase_10	AC	48 ms; 7,140 KB
testcase_11	AC	151 ms; 7,648 KB
testcase_12	AC	206 ms; 9,184 KB
testcase_13	AC	211 ms; 8,636 KB
testcase_14	AC	200 ms; 7,772 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	194 ms; 7,776 KB
testcase_24	WA	-
testcase_25	AC	211 ms; 9,432 KB
testcase_26	AC	172 ms; 7,260 KB

コンパイルメッセージ

main.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-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;
		}
	}
}