제출 #1369695

#제출 시각아이디문제언어결과실행 시간메모리
1369695gelastropodMi Teleférico (JOI25_ho_t3)C++20
100 / 100
1163 ms81640 KiB
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct node {
	int s, e, m, v;
	node* l, * r;

	node(int _s, int _e) : s(_s), e(_e), m((_s + _e) / 2), v(1e15) {
		if (s != e)
			l = new node(s, m),
			r = new node(m + 1, e);
	}

	void upd(int n, int x) {
		if (s == e) {
			v = x;
			return;
		}
		if (n <= m) l->upd(n, x);
		else r->upd(n, x);
		v = min(l->v, r->v);
	}

	int qry(int a, int b) {
		if (b < s || a > e) return 1e15;
		if (a <= s && b >= e) return v;
		return min(l->qry(a, b), r->qry(a, b));
	}
} *root;

signed main() {
	int N, M, P, Q, a, b, c, sum = 0, crntr = 0; cin >> N >> M >> P;
	vector<int> u, minr, settled(N, 0), lastocc(N, -1);
	vector<vector<int>> vals(N, vector<int>()), ovals;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c; a--, b--, c--;
		u.push_back(c);
		vals[b].push_back(c);
	}
	sort(u.begin(), u.end());
	u.erase(unique(u.begin(), u.end()), u.end());
	minr.resize(u.size(), 1e15);
	ovals.resize(u.size(), {});
	root = new node(0, u.size() - 1);
	for (int i = 1; i < N; i++) {
		if (vals[i].empty()) {
			cin >> Q;
			for (int i = 0; i < Q; i++) cout << "No\n";
			return 0;
		}
		for (int j = 0; j < (int)vals[i].size(); j++) {
			vals[i][j] = lower_bound(u.begin(), u.end(), vals[i][j]) - u.begin();
			ovals[vals[i][j]].push_back(i);
		}
	}
	for (int i = 0; i < (int)u.size(); i++) {
		while (sum < N - 1 && crntr < (int)u.size()) {
			for (int j : ovals[crntr]) {
				lastocc[j] = crntr;
				if (!settled[j]) settled[j] = 1, sum++;
			}
			crntr++;
		}
		if (sum < N - 1 && crntr == (int)u.size()) break;
		minr[i] = u[crntr - 1];
		root->upd(i, u[crntr - 1] - u[i]);
		for (int j : ovals[i]) if (lastocc[j] == i && settled[j]) settled[j] = 0, sum--;
	}
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		cin >> a >> b >> c; a--, b--;
		auto iter1 = upper_bound(u.begin(), u.end(), a);
		auto iter2 = lower_bound(minr.begin(), minr.end(), b);
		int ans = root->qry(iter2 - minr.begin(), iter1 - u.begin() - 1);
		if (iter2 != minr.begin()) ans = min(ans, b - u[iter2 - minr.begin() - 1]);
		if (iter1 != u.end()) ans = min(ans, minr[iter1 - u.begin()] - a);
		cout << (ans - (b - a) <= c ? "Yes" : "No") << '\n';
	}
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…