oj.uz

Submission #383727

# Submission time Handle Problem Language Result Execution time Memory
383727 2021-03-30T17:45:50 Z MODDI Fountain (eJOI20_fountain) C++14
100 / 100
 903 ms 19040 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
const int MAXN = 100050;
const int LOG = 20;
int diameter[MAXN], liters[MAXN], up[MAXN][LOG], sum[MAXN][LOG];
int main(){
	int n, q;
	cin>>n>>q;
	for(int i = 1; i <= n; i++){
		cin>>diameter[i]>>liters[i];
	}
	priority_queue<pii> pq;
	for(int i = 1; i <= n; i++){
		while(!pq.empty() && -pq.top().first < diameter[i])
			up[pq.top().second][0] = i, pq.pop();
			
		pq.push({-diameter[i], i});
	}
	while(!pq.empty())
		up[pq.top().second][0] = 0, pq.pop();
	
	for(int i = 1; i <= n; i++)
		sum[i][0] = liters[i];
	for(int j = 1; j < LOG; j++){
		for(int i = 0; i <= n; i++){
			up[i][j] =up[up[i][j-1]][j-1];
			sum[i][j] = sum[i][j-1] + sum[up[i][j-1]][j-1];
		}
	}
	while(q--){
		int a, b;
		cin>>a>>b;
		for(int j = LOG - 1; j >= 0; j--){
			if(sum[a][j] >= b)
				continue;
			b -= sum[a][j];
			a = up[a][j];
		}
		cout<<a<<endl;
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 5 ms 492 KB Output is correct
4 Correct 5 ms 492 KB Output is correct
5 Correct 8 ms 492 KB Output is correct
6 Correct 7 ms 492 KB Output is correct
7 Correct 7 ms 492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 16732 KB Output is correct
2 Correct 665 ms 15596 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 5 ms 492 KB Output is correct
4 Correct 5 ms 492 KB Output is correct
5 Correct 8 ms 492 KB Output is correct
6 Correct 7 ms 492 KB Output is correct
7 Correct 7 ms 492 KB Output is correct
8 Correct 587 ms 16732 KB Output is correct
9 Correct 665 ms 15596 KB Output is correct
10 Correct 7 ms 492 KB Output is correct
11 Correct 357 ms 10092 KB Output is correct
12 Correct 903 ms 18156 KB Output is correct
13 Correct 801 ms 18412 KB Output is correct
14 Correct 752 ms 18200 KB Output is correct
15 Correct 692 ms 19040 KB Output is correct