| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 51205 | zetapi | New Home (APIO18_new_home) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define itr ::iterator
typedef pair<int,int> pii;
const int MAX=5e5;
const int INF=1e8;
vector<int> vec[MAX];
vector<pii> increasing,decreasing;
int N,K,Q,X,Y,Z,l,r,pre,res[INF+9];
bool cmp(pii X,pii Y)
{
return X.first>Y.first;
}
signed main()
{
ios_base::sync_with_stdio(false);
/*cin.tie(0);
cout.tie(0);*/
cin>>N>>K>>Q;
for(int A=1;A<=N;A++)
{
cin>>X>>Y>>Z>>Z;
vec[Y].pb(X);
}
cin>>Q;
while(Q--)
{
cin>>X>>Y;
lol.pb(X);
}
lol.pb(0);
lol.pb(INF+1);
sort(lol.begin(),lol.end());
for(int A=lol.size()-2;A>0;A--)
nxt[lol[A]]=lol[A+1],
pre[lol[A]]=lol[A-1];
for(int A=1;A<=K;A++)
{
if(vec[A].empty())
continue;
sort(vec[A].begin(),vec[A].end());
for(int B=1;B<vec[A].size();B++)
increasing.pb(mp(vec[A][B-1],(vec[A][B-1]+vec[A][B])/2));
for(int B=vec[A].size()-2;B>=0;B--)
decreasing.pb(mp(vec[A][B+1],(vec[A][B+1]+vec[A][B]+1)/2));
/*for(int B=vec[A][0],C=0;B>=0;B--,C++)
res[B]=max(res[B],C);
for(int B=vec[A].back(),C=0;B<=INF;B++,C++)
res[B]=max(res[B],C);
for(int B=0;B<lol.size();B++)
{
if(lol[B]>vec[A][0])
break;
res[lol[B]]=max(res[lol[B]],vec[A][0]-lol[B]);
}
for(int)*/
}
sort(increasing.begin(),increasing.end());
sort(decreasing.begin(),decreasing.end(),cmp);
/*for(auto A:increasing)
cout<<A.first<<" inc "<<A.second<<"\n";
for(auto A:decreasing)
cout<<A.first<<" dec "<<A.second<<"\n";*/
for(int A=0;A<increasing.size();A++)
{
l=max(pre+1,increasing[A].first);
r=increasing[A].second;
for(int B=l,C=l-increasing[A].first;B<=r;B++,C++)
res[B]=max(res[B],C);
}
pre=INF+99;
for(int A=decreasing.size()-1;A>=0;A--)
{
l=min(pre-1,decreasing[A].first);
r=decreasing[A].second;
for(int B=l,C=decreasing[A].first-l;B>=r;B--,C++)
res[B]=max(res[B],C);
}
while(Q--)
{
cin>>X>>Y;
cout<<res[Y]<<"\n";
}
return 0;
}