Submission #913921

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
913921	2024-01-20T13:48:00 Z	LCJLY	Fountain (eJOI20_fountain)	C++14	30 / 100	909 ms	524288 KB

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++){
		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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-