oj.uz

답안 #911442

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911442 2024-01-19T00:26:51 Z Wendidiask Fountain (eJOI20_fountain) C++14
60 / 100
 522 ms 47396 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>
const int MS = 1e5, LOG = 20;
int twok[MS][LOG], sum[MS][LOG], d[MS], c[MS], nearest[MS];
vector<int> adj[MS];
void dfs(int x, int par) {
	for (int k = 0; k < LOG-1; k++) {
		twok[x][k+1] = twok[twok[x][k]][k];
		sum[x][k+1] = sum[x][k]+sum[twok[x][k]][k];
	}
	for (auto u : adj[x]) {
		if (u == par) continue;
		twok[u][0] = x; sum[u][0] = c[u];
		dfs(u, x);
	}
}

void solve() {
	int n, q; cin >> n >> q;
	d[0] = 0; c[0] = 0;
	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);
	}
	nearest[0] = 0;
	for (auto i : v) nearest[i] = 0;
	for (int i = 0; i <= n; i++) {
		adj[i].push_back(nearest[i]);
		adj[nearest[i]].push_back(i);
	}
	memset(twok, 0, sizeof(twok));
	memset(sum, 0, sizeof(sum)); 
	dfs(0, -1);
	/*for (int i = 0; i <= n; i++) {
		debug(i);
		for (int j = 0; j < LOG; j++) cout << sum[i][j] << " ";
		cout << '\n';
	}*/
	//cout << "---------------------------------------------------------------\n";
	while (q--) {
		int r, v;
		cin >> r >> v;
		for (int k = LOG-1; k >= 0; k--) {
			if (sum[r][k] < v) {
				v -= sum[r][k];
				r = twok[r][k];
			}
		}
		cout << r << '\n';
	}
}
int32_t main() {
	
	int tc = 1;
	//cin >> tc;
	while (tc--) {solve();}
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 36444 KB Output is correct
2 Correct 8 ms 36444 KB Output is correct
3 Correct 9 ms 36444 KB Output is correct
4 Correct 10 ms 36440 KB Output is correct
5 Correct 10 ms 36444 KB Output is correct
6 Correct 11 ms 36508 KB Output is correct
7 Correct 10 ms 36444 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 505 ms 47396 KB Output is correct
2 Correct 522 ms 46928 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 36444 KB Output is correct
2 Correct 8 ms 36444 KB Output is correct
3 Correct 9 ms 36444 KB Output is correct
4 Correct 10 ms 36440 KB Output is correct
5 Correct 10 ms 36444 KB Output is correct
6 Correct 11 ms 36508 KB Output is correct
7 Correct 10 ms 36444 KB Output is correct
8 Correct 505 ms 47396 KB Output is correct
9 Correct 522 ms 46928 KB Output is correct
10 Correct 11 ms 36440 KB Output is correct
11 Correct 227 ms 39760 KB Output is correct
12 Runtime error 56 ms 19536 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -