제출 #1269386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269386		MateiKing80	Tower (JOI24_tower)	C++20	25 / 100	444 ms	9688 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll inf = 1e13;


#define int ll


using pii = pair<int, int>;
#define fr first
#define sc second

signed main() {
	int n, q, d, a, b;
	cin >> n >> q >> d >> a >> b;
	//a = 1, b = d;
	vector<pii> inter;
	for (int i = 1; i <= n; i ++) {
		int x, y;
		cin >> x >> y;
		inter.push_back({x, y});
	}
	vector<pii> good;
	good.push_back({0, inter[0].fr - 1});
	for (int i = 0; i < n; i ++) {
		int pos = -1;
		for (int pas = 1 << 20; pas; pas >>= 1) {
			if (pos + pas < (int)good.size() && good[pos + pas].sc + d < inter[i].sc + 1)
				pos += pas;
		}
		pos ++;
		if (pos < (int)good.size()) {
			int start = good[pos].fr + d;
			start = max(start, inter[i].sc + 1);
			if (i < n - 1 && start <= inter[i + 1].fr - 1)
				good.push_back({start, inter[i + 1].fr - 1});
			else if (i == n - 1)
				good.push_back({start, inf});
		}
	}
	for (int i = 0; i < q; i ++) {
		int x;
		cin >> x; //s-ar putea sa fie ocupat x
		int pos = -1;
		for (int pas = 1 << 20; pas; pas >>= 1)
			if (pos + pas < (int)good.size() && good[pos + pas].fr <= x)
				pos += pas;
		if (pos != -1 && x <= good[pos].sc)
			cout << x << '\n';
		else
			cout << -1 << '\n';
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 38
• Subtask 3: 25 / 25
• Subtask 4: 0 / 32