oj.uz

답안 #911812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911812 2024-01-19T05:28:33 Z Wendidiask Fountain (eJOI20_fountain) C++14
100 / 100
 889 ms 34148 KB 
/*
  ____       _      _                  _                    _               _                        _     _                  _          _____ _     _             
 |  _ \     (_)    | |                (_)                  | |             (_)                      | |   | |                (_)        / ____| |   (_)            
 | |_) | ___ _  ___| |__   ___ _ __    _ ___    __ _    ___| | __ _ ___ ___ _  ___   _ __  _ __ ___ | |__ | | ___ _ __ ___    _ _ __   | |    | |__  _ _ __   __ _ 
 |  _ < / _ \ |/ __| '_ \ / _ \ '_ \  | / __|  / _` |  / __| |/ _` / __/ __| |/ __| | '_ \| '__/ _ \| '_ \| |/ _ \ '_ ` _ \  | | '_ \  | |    | '_ \| | '_ \ / _` |
 | |_) |  __/ | (__| | | |  __/ | | | | \__ \ | (_| | | (__| | (_| \__ \__ \ | (__  | |_) | | | (_) | |_) | |  __/ | | | | | | | | | | | |____| | | | | | | | (_| |
 |____/ \___|_|\___|_| |_|\___|_| |_| |_|___/  \__,_|  \___|_|\__,_|___/___/_|\___| | .__/|_|  \___/|_.__/|_|\___|_| |_| |_| |_|_| |_|  \_____|_| |_|_|_| |_|\__,_|
                                                                                    | |                                                                            
                                                                                    |_|                                                                            
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define debug(x) cerr << #x << " is " << x << "\n";
#define hehe ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repb(i, a, b) for (int i = b; i >= a; i--)
#define pii pair<int, int>
#define linebreak cout << "---------------------------------------------------------\n";
const int MS = 1e5+5, LOG = 20;
int twok[MS][LOG], d[MS], c[MS], nearest[MS], pref[MS];
vector<int> adj[MS];
void dfs(int x, int par) {
	for (int k = 0; k < LOG; k++) {
		if (twok[x][k] == -1) break;
		if (twok[twok[x][k]][k] != -1) {
			twok[x][k+1] = twok[twok[x][k]][k];
		}
	}
	for (auto u : adj[x]) {
		if (u == par) continue;
		twok[u][0] = x;
		dfs(u, x);
	}
}
int sum(int a, int b) {
	if (twok[a][0] == -1) return pref[b];
	return pref[b]-pref[twok[a][0]];
}
void solve() {
	int n, q; cin >> n >> q;
	d[0] = 1e18; c[0] = 1e18;
	for (int i = 1; i <= n; i++) cin >> d[i] >> c[i];
	vector<int> v;
	for (int i = 1; i <= n; i++) {
		if (v.empty()) {v.push_back(i); continue;}
		while (!v.empty() and d[v.back()] < d[i]) {
			nearest[v.back()] = i;
			v.pop_back();
		}
		v.push_back(i);
	}
	for (auto i : v) nearest[i] = 0;
	for (int i = 1; i <= n; i++) {
		adj[i].push_back(nearest[i]);
		adj[nearest[i]].push_back(i);
	}
	memset(twok, -1, sizeof(twok));
	dfs(0, -1);
	int vis[MS];
	queue<int> qq;
	qq.push(0);
	pref[0] = 0;
	memset(vis, 0, sizeof(vis));
	vis[0] = 1;
	while (!qq.empty()) {
		int cur = qq.front();
		qq.pop();
		for (auto v : adj[cur]) {
			if (!vis[v]) {
				vis[v] = 1;
				qq.push(v);
				pref[v] = pref[cur]+c[v];
			}
		}
	}

	while (q--) {
		int r, v;
		cin >> r >> v;
		if (c[r] >= v) {
			cout << r << '\n'; continue; 
		}
		int original = r;
		for (int k = LOG-1; k >= 0; k--) {
			int temp = -1;
			if (r != -1) temp = twok[r][k]; 
			if (temp != -1 and sum(temp, original) < v) {
				r = temp;
			}
		}
		if (r == -1 or twok[r][0] == -1) cout << 0 << '\n';
		else cout << twok[r][0] << '\n';
	}
}
int32_t main() {
	int tc = 1;
	//cin >> tc;
	while (tc--) {solve();}
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 22104 KB Output is correct
2 Correct 7 ms 22360 KB Output is correct
3 Correct 7 ms 22364 KB Output is correct
4 Correct 8 ms 22364 KB Output is correct
5 Correct 9 ms 22360 KB Output is correct
6 Correct 11 ms 22404 KB Output is correct
7 Correct 9 ms 22364 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 587 ms 30320 KB Output is correct
2 Correct 801 ms 29796 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 22104 KB Output is correct
2 Correct 7 ms 22360 KB Output is correct
3 Correct 7 ms 22364 KB Output is correct
4 Correct 8 ms 22364 KB Output is correct
5 Correct 9 ms 22360 KB Output is correct
6 Correct 11 ms 22404 KB Output is correct
7 Correct 9 ms 22364 KB Output is correct
8 Correct 587 ms 30320 KB Output is correct
9 Correct 801 ms 29796 KB Output is correct
10 Correct 9 ms 22364 KB Output is correct
11 Correct 250 ms 25428 KB Output is correct
12 Correct 889 ms 34148 KB Output is correct
13 Correct 500 ms 31588 KB Output is correct
14 Correct 459 ms 30084 KB Output is correct
15 Correct 387 ms 31564 KB Output is correct