| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 299653 | 2020-09-15T11:52:06 Z | E869120 | Trampoline (info1cup20_trampoline) | C++14 | 1384 ms | 69116 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 (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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 16 ms | 8448 KB | 200 token(s): yes count is 21, no count is 179 |
| 2 | Correct | 18 ms | 8696 KB | 200 token(s): yes count is 70, no count is 130 |
| 3 | Correct | 13 ms | 8064 KB | 197 token(s): yes count is 25, no count is 172 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 572 ms | 49396 KB | 4000 token(s): yes count is 99, no count is 3901 |
| 2 | Correct | 607 ms | 49520 KB | 4000 token(s): yes count is 91, no count is 3909 |
| 3 | Correct | 591 ms | 49008 KB | 4000 token(s): yes count is 4000, no count is 0 |
| 4 | Correct | 609 ms | 49388 KB | 4000 token(s): yes count is 1991, no count is 2009 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 736 ms | 52628 KB | 200000 token(s): yes count is 110486, no count is 89514 |
| 2 | Correct | 789 ms | 52808 KB | 200000 token(s): yes count is 114664, no count is 85336 |
| 3 | Correct | 831 ms | 52456 KB | 200000 token(s): yes count is 86232, no count is 113768 |
| 4 | Correct | 887 ms | 52460 KB | 200000 token(s): yes count is 94603, no count is 105397 |
| 5 | Correct | 896 ms | 52748 KB | 200000 token(s): yes count is 94148, no count is 105852 |
| 6 | Correct | 985 ms | 53660 KB | 200000 token(s): yes count is 97163, no count is 102837 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 16 ms | 7936 KB | 5000 token(s): yes count is 3238, no count is 1762 |
| 2 | Correct | 16 ms | 7936 KB | 5000 token(s): yes count is 3837, no count is 1163 |
| 3 | Correct | 20 ms | 8148 KB | 5000 token(s): yes count is 4104, no count is 896 |
| 4 | Correct | 16 ms | 7936 KB | 5000 token(s): yes count is 3934, no count is 1066 |
| 5 | Correct | 20 ms | 7936 KB | 5000 token(s): yes count is 3384, no count is 1616 |
| 6 | Correct | 15 ms | 7936 KB | 5000 token(s): yes count is 3390, no count is 1610 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1163 ms | 54148 KB | 200000 token(s): yes count is 171404, no count is 28596 |
| 2 | Correct | 1049 ms | 52972 KB | 200000 token(s): yes count is 161254, no count is 38746 |
| 3 | Correct | 874 ms | 63980 KB | 200000 token(s): yes count is 117455, no count is 82545 |
| 4 | Correct | 1384 ms | 69116 KB | 200000 token(s): yes count is 182118, no count is 17882 |
| 5 | Correct | 1004 ms | 65588 KB | 200000 token(s): yes count is 167565, no count is 32435 |
| 6 | Correct | 886 ms | 64112 KB | 200000 token(s): yes count is 156797, no count is 43203 |
| 7 | Correct | 893 ms | 64228 KB | 200000 token(s): yes count is 156797, no count is 43203 |
| 8 | Correct | 871 ms | 64188 KB | 200000 token(s): yes count is 122100, no count is 77900 |
| 9 | Correct | 1128 ms | 65308 KB | 200000 token(s): yes count is 139670, no count is 60330 |
| 10 | Correct | 1132 ms | 65260 KB | 200000 token(s): yes count is 165806, no count is 34194 |
| 11 | Correct | 1208 ms | 67112 KB | 200000 token(s): yes count is 175646, no count is 24354 |
| 12 | Correct | 661 ms | 64528 KB | 200000 token(s): yes count is 134695, no count is 65305 |
| 13 | Correct | 736 ms | 64236 KB | 200000 token(s): yes count is 126733, no count is 73267 |
| 14 | Correct | 932 ms | 64252 KB | 200000 token(s): yes count is 155290, no count is 44710 |
| 15 | Correct | 775 ms | 64528 KB | 200000 token(s): yes count is 129674, no count is 70326 |