oj.uz

Submission #299651

# Submission time Handle Problem Language Result Execution time Memory
299651 2020-09-15T11:47:42 Z E869120 Trampoline (info1cup20_trampoline) C++14
54 / 100
 1183 ms 65536 KB 
#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 (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

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

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8448 KB 200 token(s): yes count is 21, no count is 179
2 Correct 17 ms 8704 KB 200 token(s): yes count is 70, no count is 130
3 Correct 13 ms 8040 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 50664 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 544 ms 50540 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 544 ms 50032 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 548 ms 50540 KB 4000 token(s): yes count is 1991, no count is 2009

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 63980 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 827 ms 64112 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 871 ms 63980 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 913 ms 64260 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 932 ms 64228 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 1014 ms 65236 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 7936 KB expected NO, found YES [16th token]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 65536 KB 200000 token(s): yes count is 171404, no count is 28596
2 Incorrect 1089 ms 64752 KB expected NO, found YES [22020th token]
3 Halted 0 ms 0 KB -