結果

問題 No.953 席
コンテスト
ユーザー %20
提出日時 2018-08-09 23:28:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,490 bytes
コンパイル時間 1,695 ms
コンパイル使用メモリ 201,932 KB
最終ジャッジ日時 2025-01-06 12:18:34
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 7 WA * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
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);
      | ^~~~

ソースコード

diff # 

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