oj.uz

Submission #383726

# Submission time Handle Problem Language Result Execution time Memory
383726 2021-03-30T17:43:05 Z MODDI Fountain (eJOI20_fountain) C++14
100 / 100
 934 ms 26344 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 = 25;
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 492 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 6 ms 620 KB Output is correct
5 Correct 8 ms 620 KB Output is correct
6 Correct 8 ms 620 KB Output is correct
7 Correct 8 ms 620 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 23532 KB Output is correct
2 Correct 687 ms 22380 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 492 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 6 ms 620 KB Output is correct
5 Correct 8 ms 620 KB Output is correct
6 Correct 8 ms 620 KB Output is correct
7 Correct 8 ms 620 KB Output is correct
8 Correct 614 ms 23532 KB Output is correct
9 Correct 687 ms 22380 KB Output is correct
10 Correct 8 ms 620 KB Output is correct
11 Correct 380 ms 14060 KB Output is correct
12 Correct 934 ms 25864 KB Output is correct
13 Correct 854 ms 25708 KB Output is correct
14 Correct 749 ms 24812 KB Output is correct
15 Correct 755 ms 26344 KB Output is correct