oj.uz

Submission #638399

# Submission time Handle Problem Language Result Execution time Memory
638399 2022-09-05T19:42:46 Z Koful123 Fountain (eJOI20_fountain) C++17
100 / 100
 110 ms 18868 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define endl "\n"
#define mod 1000000007
#define int long long
#define double long double
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

void solve(){		

	int n,t;
	cin >> n >> t;

	vector<pair<int,int>> v(n),q[n];
	for(auto &[x,y] : v){
		cin >> x >> y;
	}

	vector<int> ans(t);
	for(int i=0;i<t;i++){
		int a,b; cin >> a >> b;
		q[a-1].pb({b,i});
	}

	vector<pair<int,pair<int,int>>> tmp;
	for(int i=n-1;i>=0;i--){
		while(tmp.size() && v[i].ff >= tmp.back().ss.ss){
			tmp.pop_back();
		}
		int add = (tmp.size() ? tmp.back().ff + v[i].ss : v[i].ss);
		tmp.push_back({add,{i,v[i].ff}});
		for(auto[x,y] : q[i]){
			if(x > add) ans[y] = 0;
			else{
				pair<int,pair<int,int>> p = {add-x,{1e18,1e18}};
				auto it = upper_bound(all(tmp),p);
				ans[y] = (*it).ss.ff + 1;
			}
		}
	}

	for(int x : ans){
		cout << x << endl;
	}
}

signed main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	int t = 1;
//	cin >> t;

	while(t--)
		solve();
	
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 14276 KB Output is correct
2 Correct 83 ms 14860 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 78 ms 14276 KB Output is correct
9 Correct 83 ms 14860 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 52 ms 8104 KB Output is correct
12 Correct 110 ms 18868 KB Output is correct
13 Correct 109 ms 16248 KB Output is correct
14 Correct 93 ms 15080 KB Output is correct
15 Correct 84 ms 15348 KB Output is correct