oj.uz

답안 #913920

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
913920 2024-01-20T13:46:20 Z LCJLY Fountain (eJOI20_fountain) C++14
0 / 100
 114 ms 27984 KB 
#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++){
		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]);
			for(auto it:se[x]){
				se[index].insert({it.first+arr[x].second-offset[x],it.second});
			}
			offset[index]+=arr[x].second;
		}
		else{
			for(auto it:se[x]){
				se[index].insert({it.first-arr[x].second-offset[x],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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 114 ms 27984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -