#include <bits/stdc++.h>
using namespace std;
/*
fie a prima trambulina din dreapta lui start
si b prima trambulina din stanga lui finish care sa se duca in sus
^ cautare binara
( caz special cand start si finish sunt pe aceeasi linie )
vrei sa stii daca poti sa ajungi de la a la b
faci precalculare ig:
precalculare: O(N*log(N))
verificare per query: O(log(N))
*/
map<int, vector<pair<int, int>>> v; // poz, indicele poz
int up[200005][35]; // binary lifting
int Find(vector<pair<int, int>>& vec, int p, bool left) // cautam prima trambulina cu poz >= p
{
int st=-1, dr=vec.size();
while(st+1 < dr)
{
int mid=(st+dr)/2;
if((!left && vec[mid].first >= p) || (left && vec[mid].first > p))
dr=mid;
else
st=mid;
}
if(left)
dr--;
return dr;
}
int post[200005]; // coloana fiecarei trambuline verzi, folosesc asta la sfarsit
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int r, c, n;
cin>>r>>c>>n;
for(int i=1; i<=n; i++)
{
int x, y;
cin>>x>>y;
post[i]=y;
v[x].push_back({y, i});
}
for(auto &it:v)
{
sort(it.second.begin(), it.second.end());
}
// precalculare
int x=0;
for(auto &it:v)
{
vector<pair<int, int>>& vec=it.second;
int l=it.first;
for(pair<int, int>& pr:vec)
{
int u=pr.second;
if(up[u][0])
{
continue;
}
int l0=l;
int p=pr.first;
int u0=u; // last u
while(true)
{
l0++;
p=Find(v[l0], post[u], false);
//cout<<u<<'\n';
if(p == v[l0].size())
{
break;
}
u=v[l0][p].second;
if(up[u][0])
break;
up[u][0]=u0;
p=v[l0][p].first;
u0=u;
}
}
}
for(int k=1; k<32; k++)
{
for(int i=1; i<=n; i++)
{
up[i][k]=up[up[i][k-1]][k-1];
}
}
//for(int i=1; i<=n; i++)
// cout<<up[i][0]<<" ";
//return 0;
// query-uri
int t;
cin>>t;
for(int i=1; i<=t; i++)
{
int x0, y0, x1, y1;
cin>>x0>>y0>>x1>>y1;
if(x1 < x0 || y1 < y0)
{
cout<<"No\n";
continue;
}
if(x0 == x1)
{
cout<<"Yes\n";
continue;
}
x1--; // ca te uiti la trambulina de sus ( amongus reference )
int a=Find(v[x0], y0, false);
int b=Find(v[x1], y1, true);
if(a == v[x0].size() || b == -1)
{
cout<<"No\n";
continue;
}
//cout<<a<<" "<<b<<'\n';
//continue;
// acum cauti al x1-x0 lea ancestor la lui b
int sus=x1-x0;
for(int j=0; j<32; j++)
{
if(sus&(1<<j))
{
b=up[b][j];
}
}
if(post[b] >= post[a])
cout<<"Yes\n";
else
cout<<"No\n";
}
return 0;
}
Compilation message
trampoline.cpp: In function 'int32_t main()':
trampoline.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if(p == v[l0].size())
| ~~^~~~~~~~~~~~~~~
trampoline.cpp:123:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | if(a == v[x0].size() || b == -1)
| ~~^~~~~~~~~~~~~~~
trampoline.cpp:58:9: warning: unused variable 'x' [-Wunused-variable]
58 | int x=0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1628 KB |
expected YES, found NO [1st token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
31732 KB |
expected YES, found NO [3rd token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
223 ms |
31432 KB |
expected NO, found YES [7th token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1112 KB |
expected YES, found NO [4th token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
456 ms |
39004 KB |
expected YES, found NO [2nd token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
