oj.uz

Submission #692264

# Submission time Handle Problem Language Result Execution time Memory
692264 2023-02-01T09:07:31 Z NeroZein Trampoline (info1cup20_trampoline) C++14
0 / 100
 2000 ms 91240 KB 
/*
 *    author: NeroZein
 *    created: 01.02.2023 11:11:00
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int r, c, t;
	cin >> r >> c >> t;
	map<int, set<pair<int,int>>> mp; 
	vector<pair<int,int>> p(t); 
	for (int i = 0; i < t; ++i) {
		cin >> p[i].first >> p[i].second; 
	}
	sort(p.begin(), p.end()); 
	for (int i = 0; i < t; ++i) {
		mp[p[i].first].insert({p[i].second, i});
	}
	const int Log = 20; 
	vector<vector<int>> dp(100005, vector<int>(Log)); 
	for (int i = 0; i < t; ++i) {
		auto se = mp[p[i].first-1]; 
		auto it = se.upper_bound(make_pair(p[i].second, 1e9)); 
		if (se.empty() || it == se.begin()) {
			dp[i][0] = -1; 
		}
		else {
			--it;
			dp[i][0] = it->second;
		}
	}
	for (int j = 1; j < Log; ++j) {
		for (int i = 0; i < t; ++i) {
			if (dp[i][j-1] == -1) {
				continue; 
			}
			dp[i][j] = dp[dp[i][j-1]][j-1];
		}
	}
	auto jump = [&](int u, int k) {
		for (int i = 0; i < Log; ++i) {
			if ((k >> i) & 1) {
				u = dp[u][i];
				if (u == -1) {
					break; 
				}
			}
		}
		return u; 
	};
	int q;
	cin >> q; 
	while(q--) {
		int xs, ys, xf, yf;
		cin >> xs >> ys >> xf >> yf; 
		if (xs > xf || ys > yf) {
			cout << "NO\n";
			continue; 
		}
		if (xs == xf) {
			cout << "YES" << '\n';
			continue; 
		}
		auto se = mp[xf-1];
		if (se.empty()) {
			cout << "NO" << '\n';
			continue; 
		}
		auto it = se.upper_bound(make_pair(xf, yf));
		if (it == se.begin()) {
			cout << "NO" << '\n';
			continue;
		}
		--it; 
		xf = it->first, xs = it->second;
		int k = xf - xs; 
		int pp = jump(xf, k); 
		cout << (pp == -1 ? "NO\n" : (p[pp].second < ys ? "NO\n" : "YES\n"));
	}
	return 0;
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 20660 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 416 ms 74156 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 42580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 41172 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 91240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -