Submission #299653

#	Time	Username	Problem	Language	Result	Execution time	Memory
299653		E869120	Trampoline (info1cup20_trampoline)	C++14	100 / 100	1384 ms	69116 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;

// Input
int H, W;
int N, X[1 << 18], Y[1 << 18];
int Q, SX[1 << 18], SY[1 << 18], EX[1 << 18], EY[1 << 18];

// Compress
map<pair<int, int>, int> Map;
vector<int> GX;
vector<int> V[1 << 18];

// Graph
int par[1 << 18][33];

bool query(int sx, int sy, int gx, int gy) {
	if (sx > gx) return false;
	if (sy > gy) return false;
	if (sx == gx) return true;
	
	int pos1 = lower_bound(GX.begin(), GX.end(), sx) - GX.begin();
	if (pos1 == (int)GX.size() || GX[pos1] != sx) return false;
	int pos2 = lower_bound(V[pos1].begin(), V[pos1].end(), sy) - V[pos1].begin();
	if (pos2 == (int)V[pos1].size()) return false;
	
	int pos = Map[make_pair(sx, V[pos1][pos2])];
	int rem = gx - sx - 1;
	for (int i = 30; i >= 0; i--) {
		if (rem >= (1 << i)) { rem -= (1 << i); pos = par[pos][i]; }
	}
	if (pos == 0) return false;
	if (Y[pos] > gy) return false;
	return true;
}

int main() {
	// Step #1. Input
	scanf("%d%d%d", &H, &W, &N);
	for (int i = 1; i <= N; i++) scanf("%d%d", &X[i], &Y[i]);
	for (int i = 1; i <= N; i++) Map[make_pair(X[i], Y[i])] = i;
	scanf("%d", &Q);
	for (int i = 1; i <= Q; i++) scanf("%d%d%d%d", &SX[i], &SY[i], &EX[i], &EY[i]);
	
	// Step #2. Compress
	for (int i = 1; i <= N; i++) GX.push_back(X[i]);
	sort(GX.begin(), GX.end());
	GX.erase(unique(GX.begin(), GX.end()), GX.end());
	for (int i = 1; i <= N; i++) {
		int pos1 = lower_bound(GX.begin(), GX.end(), X[i]) - GX.begin();
		V[pos1].push_back(Y[i]);
	}
	for (int i = 0; i < (int)GX.size(); i++) {
		sort(V[i].begin(), V[i].end());
	}
	
	// Step #3. Make Graph
	for (int i = 1; i <= N; i++) {
		int pos1 = lower_bound(GX.begin(), GX.end(), X[i] + 1) - GX.begin();
		if (pos1 == (int)GX.size() || GX[pos1] != X[i] + 1) continue;
		int pos2 = lower_bound(V[pos1].begin(), V[pos1].end(), Y[i]) - V[pos1].begin();
		if (pos2 == (int)V[pos1].size()) continue;
		int idx = Map[make_pair(X[i] + 1, V[pos1][pos2])];
		par[i][0] = idx;
	}
	for (int i = 1; i <= 32; i++) {
		for (int j = 1; j <= N; j++) par[j][i] = par[par[j][i - 1]][i - 1];
	}
	
	// Step #4. Answer Query
	for (int i = 1; i <= Q; i++) {
		bool I = query(SX[i], SY[i], EX[i], EY[i]);
		if (I == true) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

Compilation message (stderr)

trampoline.cpp: In function 'int main()':
trampoline.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%d%d%d", &H, &W, &N);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
trampoline.cpp:40:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  for (int i = 1; i <= N; i++) scanf("%d%d", &X[i], &Y[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
trampoline.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
trampoline.cpp:43:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  for (int i = 1; i <= Q; i++) scanf("%d%d%d%d", &SX[i], &SY[i], &EX[i], &EY[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 27 / 27