oj.uz

Submission #913927

# Submission time Handle Problem Language Result Execution time Memory
913927 2024-01-20T13:56:31 Z LCJLY Fountain (eJOI20_fountain) C++14
100 / 100
 270 ms 47184 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++){
		//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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 26476 KB Output is correct
2 Correct 161 ms 31468 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 140 ms 26476 KB Output is correct
9 Correct 161 ms 31468 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 93 ms 22004 KB Output is correct
12 Correct 270 ms 42576 KB Output is correct
13 Correct 261 ms 47184 KB Output is correct
14 Correct 194 ms 41552 KB Output is correct
15 Correct 158 ms 30000 KB Output is correct