oj.uz

Submission #812842

# Submission time Handle Problem Language Result Execution time Memory
812842 2023-08-07T11:20:31 Z OAleksa Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 38104 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std; 
const int maxn = 1e5 + 69;
const int lg = 18;
long long up[maxn][lg], sm[maxn][lg];
vector<int> g[maxn];
vector<int> d(maxn), l(maxn), vis(maxn);
int n, q;

void dfs(int v) {
	vis[v] = true;
	if(!g[v].empty()) {
		dfs(g[v].front());
		up[v][0] = g[v].front();
		sm[v][0] = l[g[v].front()];
		for(int i = 1;i < lg;i++) {
			up[v][i] = up[up[v][i - 1]][i - 1];
			sm[v][i] = sm[v][i - 1] + sm[up[v][i - 1]][i - 1];
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while(tt--) {
		cin >> n >> q;
		for(int i = 1;i <= n;i++) 
			cin >> d[i] >> l[i];
		l[n + 1] = 1e9;
		vector<pair<int, int>> st;
		st.push_back({1e9, n + 1});
		for(int i = n;i >= 1;i--) {
			while(!st.empty() && st.back().f <= d[i])
				st.pop_back();
			if(!st.empty()) 
				g[i].push_back(st.back().s);
			st.push_back({d[i], i});
		}
		for(int i = 1;i <= n;i++) 
			if(!vis[i]) 
				dfs(i);
		for(int i = 0;i < q;i++) {
			int v, r;
			cin >> v >> r;
			int u = v;
			if(r > l[v]) {
				r -= l[v];
				for(int j = lg - 1;j >= 0;j--) {
					if(sm[u][j] <= r) {
						r -= sm[u][j];
						u = up[u][j];
					}
				}
				if(r > 0)
					u = up[u][0];
			}
			if(u == n + 1)
				u = 0;
			cout << u << "\n";
		}
	}
   return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 6 ms 4180 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 38104 KB Output is correct
2 Correct 206 ms 35528 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 6 ms 4180 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 171 ms 38104 KB Output is correct
9 Correct 206 ms 35528 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Execution timed out 1580 ms 14972 KB Time limit exceeded
12 Halted 0 ms 0 KB -