#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a,b) for (int a = 0; a < (b); ++a)
#define pb push_back
#define all(t) t.begin(), t.end()
struct Pole
{
int y=-1, x=-1;
};
struct Element
{
int val, idx;
bool operator < (const Element &element) const
{
return val < element.val;
}
};
const int max_N = 2e5+5, lg_SIZE = 18;
int wysokosc = 0, szerokosc = 0, n = 0, q = 0, y_1 = 0, y_2 = 0, x_1 = 0, x_2 = 0;
Pole P[max_N];
int nextt[max_N];
map<int,set<Element>> S;
int jump[max_N][lg_SIZE+1];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> wysokosc >> szerokosc >> n;
rep(i,n) cin >> P[i].y >> P[i].x;
rep(i,n) S[P[i].y].insert({P[i].x,i});
rep(i,n)
{
int y = P[i].y, x = P[i].x;
if (auto it = S.find(y+1) == S.end())
{
jump[i][0] = i;
continue;
}
auto it = S[y+1].lower_bound({x,-1});
if (it != S[y+1].end()) jump[i][0] = it->idx;
else jump[i][0] = i;
}
for (int i = 1; i <= lg_SIZE; ++i)
{
rep(j,n)
{
int val = jump[j][i-1];
jump[j][i] = jump[val][i-1];
}
}
cin >> q;
rep(z,q)
{
cin >> y_1 >> x_1 >> y_2 >> x_2;
if (y_1 > y_2 or x_1 > x_2)
{
cout << "No" << '\n';
continue;
}
if (y_1 == y_2)
{
cout << "Yes" << '\n';
continue;
}
if (auto it = S.find(y_1) == S.end())
{
cout << "No" << '\n';
continue;
}
if (auto it = S[y_1].lower_bound({x_1,-1}) == S[y_1].end())
{
cout << "No" << '\n';
continue;
}
int akt = (S[y_1].lower_bound({x_1,-1}))->idx, y = P[akt].y, x = P[akt].x;
bool czy_OK = false;
for (int i = lg_SIZE; i >= 0; --i)
{
int v = jump[akt][i];
if(P[v].y <= y_2-1) akt = v;
}
if((P[akt].y == y_2 or P[akt].y == y_2-1) and P[akt].x <= x_2) cout << "Yes" << '\n';
else cout << "No" << '\n';
/*
while(y < y_2)
{
++y;
if (y > wysokosc) break;
if (y == y_2 and x <= x_2)
{
czy_OK = true;
break;
}
if (nextt[akt] == -1) break;
akt = nextt[akt], x = P[akt].x;
}
if (czy_OK == true) cout << "Yes" << '\n';
else cout << "No" << '\n';
*/
}
return 0;
}
Compilation message
trampoline.cpp: In function 'int main()':
trampoline.cpp:41:18: warning: unused variable 'it' [-Wunused-variable]
41 | if (auto it = S.find(y+1) == S.end())
| ^~
trampoline.cpp:72:18: warning: unused variable 'it' [-Wunused-variable]
72 | if (auto it = S.find(y_1) == S.end())
| ^~
trampoline.cpp:77:18: warning: unused variable 'it' [-Wunused-variable]
77 | if (auto it = S[y_1].lower_bound({x_1,-1}) == S[y_1].end())
| ^~
trampoline.cpp:82:56: warning: unused variable 'y' [-Wunused-variable]
82 | int akt = (S[y_1].lower_bound({x_1,-1}))->idx, y = P[akt].y, x = P[akt].x;
| ^
trampoline.cpp:82:70: warning: unused variable 'x' [-Wunused-variable]
82 | int akt = (S[y_1].lower_bound({x_1,-1}))->idx, y = P[akt].y, x = P[akt].x;
| ^
trampoline.cpp:83:14: warning: unused variable 'czy_OK' [-Wunused-variable]
83 | bool czy_OK = false;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3672 KB |
200 token(s): yes count is 21, no count is 179 |
| 2 |
Correct |
6 ms |
5724 KB |
200 token(s): yes count is 70, no count is 130 |
| 3 |
Correct |
4 ms |
3420 KB |
197 token(s): yes count is 25, no count is 172 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
26660 KB |
4000 token(s): yes count is 99, no count is 3901 |
| 2 |
Correct |
188 ms |
26644 KB |
4000 token(s): yes count is 91, no count is 3909 |
| 3 |
Correct |
221 ms |
26384 KB |
4000 token(s): yes count is 4000, no count is 0 |
| 4 |
Correct |
175 ms |
26480 KB |
4000 token(s): yes count is 1991, no count is 2009 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
309 ms |
27012 KB |
200000 token(s): yes count is 110486, no count is 89514 |
| 2 |
Correct |
422 ms |
27072 KB |
200000 token(s): yes count is 114664, no count is 85336 |
| 3 |
Correct |
442 ms |
27184 KB |
200000 token(s): yes count is 86232, no count is 113768 |
| 4 |
Correct |
493 ms |
27216 KB |
200000 token(s): yes count is 94603, no count is 105397 |
| 5 |
Correct |
513 ms |
27204 KB |
200000 token(s): yes count is 94148, no count is 105852 |
| 6 |
Correct |
632 ms |
33368 KB |
200000 token(s): yes count is 97163, no count is 102837 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3164 KB |
5000 token(s): yes count is 3238, no count is 1762 |
| 2 |
Correct |
6 ms |
3164 KB |
5000 token(s): yes count is 3837, no count is 1163 |
| 3 |
Correct |
7 ms |
3652 KB |
5000 token(s): yes count is 4104, no count is 896 |
| 4 |
Correct |
5 ms |
3164 KB |
5000 token(s): yes count is 3934, no count is 1066 |
| 5 |
Correct |
8 ms |
3164 KB |
5000 token(s): yes count is 3384, no count is 1616 |
| 6 |
Correct |
5 ms |
3164 KB |
5000 token(s): yes count is 3390, no count is 1610 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
873 ms |
34736 KB |
200000 token(s): yes count is 171404, no count is 28596 |
| 2 |
Correct |
625 ms |
37748 KB |
200000 token(s): yes count is 161254, no count is 38746 |
| 3 |
Correct |
389 ms |
35868 KB |
200000 token(s): yes count is 117455, no count is 82545 |
| 4 |
Correct |
812 ms |
54544 KB |
200000 token(s): yes count is 182118, no count is 17882 |
| 5 |
Correct |
475 ms |
42580 KB |
200000 token(s): yes count is 167565, no count is 32435 |
| 6 |
Correct |
364 ms |
35896 KB |
200000 token(s): yes count is 156797, no count is 43203 |
| 7 |
Correct |
394 ms |
35976 KB |
200000 token(s): yes count is 156797, no count is 43203 |
| 8 |
Correct |
342 ms |
35688 KB |
200000 token(s): yes count is 122100, no count is 77900 |
| 9 |
Correct |
604 ms |
42032 KB |
200000 token(s): yes count is 139670, no count is 60330 |
| 10 |
Correct |
644 ms |
42148 KB |
200000 token(s): yes count is 165806, no count is 34194 |
| 11 |
Correct |
650 ms |
48328 KB |
200000 token(s): yes count is 175646, no count is 24354 |
| 12 |
Correct |
292 ms |
35668 KB |
200000 token(s): yes count is 134695, no count is 65305 |
| 13 |
Correct |
300 ms |
36004 KB |
200000 token(s): yes count is 126733, no count is 73267 |
| 14 |
Correct |
380 ms |
35892 KB |
200000 token(s): yes count is 155290, no count is 44710 |
| 15 |
Correct |
306 ms |
35856 KB |
200000 token(s): yes count is 129674, no count is 70326 |
