제출 #913927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
913927		LCJLY	Fountain (eJOI20_fountain)	C++14	100 / 100	270 ms	47184 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;

void solve(){	
	int n,q;
	cin >> n >> q;
	
	pii arr[n+1]; //diameter capacity
	for(int x=0;x<n;x++){
		cin >> arr[x].first >> arr[x].second;
	}
	arr[n]={1e12,1e18};
	
	int nxt[n];
	deque<int>d;
	d.push_back(n);
	for(int x=n-1;x>=0;x--){
		while(!d.empty()&&arr[x].first>=arr[d.back()].first) d.pop_back();
		nxt[x]=d.back();
		d.push_back(x);
	}
	
	int ans[q];
	pii que[q];
	set<pii>se[n+5];
	for(int x=0;x<q;x++){
		cin >> que[x].first >> que[x].second;
		se[que[x].first-1].insert({que[x].second,x});
	}	
	
	int offset[n+5];
	memset(offset,0,sizeof(offset));
	for(int x=0;x<=n;x++){
		//for(auto it:se[x]){
			//cout << it.first-offset[]
		//}
		while(!se[x].empty()&&se[x].begin()->first-offset[x]<=arr[x].second){
			pii hold=*se[x].begin();
			se[x].erase(se[x].begin());
			ans[hold.second]=x;
		}
		
		int index=nxt[x];
		if(se[x].size()>se[index].size()){
			swap(se[index],se[x]);
			swap(offset[index],offset[x]);
			offset[index]+=arr[x].second;
			for(auto it:se[x]){
				se[index].insert({it.first+offset[index]-offset[x],it.second});
			}
		}
		else{
			for(auto it:se[x]){
				se[index].insert({it.first+offset[index]-offset[x]-arr[x].second,it.second});
			}
		}
	}
	
	for(int x=0;x<q;x++){
		cout << (ans[x]+1)%(n+1) << "\n";
	}
	
	
}
 
int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40