#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
int r,c,n;
int a[200001];
int b[200001];
vector<pair<int,int>> lin[800001];
int anc[200001][19];
map<int,int> mapl;
map<int,int> norml;
int cntn=0;
void normalizare()
{
for(int i=1;i<=n;i++)
{
mapl[a[i]]++;
mapl[a[i]-1]++;
mapl[a[i]+1]++;
}
int val;
for(auto it:mapl)
{
cntn++;
norml[it.first]=cntn;
}
for(int i=1;i<=n;i++)
a[i]=norml[a[i]];
}
bool query(int lins, int cols, int linf, int colf)
{
///returneaza colf
if(lins>linf)
return 0;
if(cols>colf)
return 0;
if(lins==linf)
return 1;
if(lin[lins].size()==0 || lin[lins][lin[lins].size()-1].first < cols)
return 0;
int st,dr,mij;
st=0;
dr=lin[lins].size()-1;
while(st<=dr)
{
mij=(st+dr)/2;
if(lin[lins][mij].first>=cols && (mij==0 || lin[lins][mij-1].first<cols))
break;
else if(lin[lins][mij].first>=cols)
dr=mij-1;
else
st=mij+1;
}
int cur = lin[lins][mij].second;
for(int i=0;i<19;i++)
{
if(((1<<i)&(linf-lins-1))!=0)
cur = anc[cur][i];
if(cur==-1)
break;
}
if(cur==-1)
return 0;
if(b[cur] <= colf)
return 1;
else
return 0;
}
int cit[200001][4];
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>r>>c>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
int q;
cin>>q;
for(int i=0;i<q;i++)
{
cin>>cit[i][0]>>cit[i][1]>>cit[i][2]>>cit[i][3];
mapl[cit[i][0]]++;
mapl[cit[i][2]]++;
}
normalizare();
for(int i=1;i<=n;i++)
{
lin[a[i]].push_back({b[i],i});
}
for(int i=1;i<=cntn;i++)
sort(lin[i].begin(),lin[i].end());
for(int i=1;i<=cntn;i++)
{
for(auto x:lin[i])
{
///calc anc[x.second][0]
if(lin[i+1].size()==0 || lin[i+1][lin[i+1].size()-1].first<x.first)
{
anc[x.second][0]=-1;
}
else
{
int st,dr,mij;
st=0;
dr=lin[i+1].size()-1;
while(st<=dr)
{
mij=(st+dr)/2;
if(lin[i+1][mij].first>=x.first && (mij==0 || lin[i+1][mij-1].first<x.first))
break;
else if(lin[i+1][mij].first>=x.first)
dr=mij-1;
else
st=mij+1;
}
anc[x.second][0] = lin[i+1][mij].second;
}
}
}
for(int put=1;put<19;put++)
{
for(int i=1;i<=cntn;i++)
{
for(auto x:lin[i])
{
///calc anc[x.second][put]
if(anc[x.second][put-1]==-1)
anc[x.second][put]=-1;
else
anc[x.second][put]=anc[anc[x.second][put-1]][put-1];
}
}
}
int lins,cols,linf,colf;
for(int i=0;i<q;i++)
{
lins = norml[cit[i][0]];
cols = cit[i][1];
linf = norml[cit[i][2]];
colf = cit[i][3];
if(query(norml[lins],cols,norml[linf],colf))
cout<<"Yes";
else
cout<<"No";
cout<<"\n";
}
return 0;
}
Compilation message
trampoline.cpp: In function 'void normalizare()':
trampoline.cpp:20:9: warning: unused variable 'val' [-Wunused-variable]
20 | int val;
| ^~~
trampoline.cpp: In function 'bool query(int, int, int, int)':
trampoline.cpp:54:28: warning: 'mij' may be used uninitialized in this function [-Wmaybe-uninitialized]
54 | int cur = lin[lins][mij].second;
| ^
trampoline.cpp: In function 'int main()':
trampoline.cpp:116:48: warning: 'mij' may be used uninitialized in this function [-Wmaybe-uninitialized]
116 | anc[x.second][0] = lin[i+1][mij].second;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
20056 KB |
expected YES, found NO [68th token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
40600 KB |
expected NO, found YES [874th token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
217 ms |
53260 KB |
expected NO, found YES [1st token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
19924 KB |
expected NO, found YES [17th token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
703 ms |
65684 KB |
expected NO, found YES [12th token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
