oj.uz

답안 #913921

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
913921 2024-01-20T13:48:00 Z LCJLY Fountain (eJOI20_fountain) C++14
30 / 100
 909 ms 524288 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<=arr[x].second){
			pii hold=*se[x].begin();
			se[x].erase(se[x].begin());
			ans[hold.second]=x;
		}
		
		int index=nxt[x];
		for(auto it:se[x]){
			se[index].insert({it.first-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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 1116 KB Output is correct
5 Correct 91 ms 42008 KB Output is correct
6 Correct 27 ms 14228 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 909 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 1116 KB Output is correct
5 Correct 91 ms 42008 KB Output is correct
6 Correct 27 ms 14228 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Runtime error 909 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -