| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 152224 | TadijaSebez | 새 집 (APIO18_new_home) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define l_type 0
#define r_type 1
const int N=300050;
const int mxx=1e8;
int x[N],t[N],a[N],b[N],qx[N],qt[N],n,q,k,ans[N],myl[N],myr[N];
struct cmp{ bool operator () (int i, int j) const { return x[i]<x[j] || (x[i]==x[j] && i<j);}};
set<int,cmp> house[N];
const int H=8*N;
int type[H],l[H],r[H],tl[H],tr[H],hsz;
int act[N],active,cur_time;
int Seg(int ty, int _l, int _r, int _tl){ hsz++;type[hsz]=ty;l[hsz]=_l;r[hsz]=_r;tl[hsz]=_tl;tr[hsz]=-1;return hsz;}
void S(int i, int j)
{
if(i==0) myr[j]=Seg(r_type,1,x[j],cur_time);
else if(j==0) myl[i]=Seg(l_type,x[i],mxx,cur_time);
else
{
int mid=x[i]+x[j]>>1;
myl[i]=Seg(l_type,x[i],mid,cur_time);
myr[i]=Seg(r_type,mid+((x[j]-x[i])%2==1),x[j],cur_time);
}
}
void E(int i, int j)
{
if(i!=0) tr[myl[i]]=cur_time-1;
if(j!=0) tr[myr[j]]=cur_time-1;
}
void Add(int i)
{
act[t[i]]++;if(act[t[i]]==1) active++;
house[t[i]].insert(i);
auto it=house[t[i]].find(i);
bool lf=0,rf=0;
auto L=it,R=it;
if(L!=house[t[i]].begin()) L--,lf=1;
R++;if(R!=house[t[i]].end()) rf=1;
if(lf && rf) E(*L,*R),S(*L,i),S(i,*R);
else if(lf) E(*L,0),S(*L,i),S(i,0);
else if(rf) E(0,*R),S(i,*R),S(0,i);
else S(0,i),S(i,0);
}
void Del(int i)
{
act[t[i]]--;if(act[t[i]]==0) active--;
auto it=house[t[i]].find(i);
bool lf=0,rf=0;
auto L=it,R=it;
if(L!=house[t[i]].begin()) L--,lf=1;
R++;if(R!=house[t[i]].end()) rf=1;
if(lf && rf) E(*L,i),E(i,*R),S(*L,*R);
else if(lf) E(*L,i),E(i,0),S(*L,0);
else if(rf) E(i,*R),E(0,i),S(0,*R);
else E(0,i),E(i,0);
house[t[i]].erase(i);
}
vector<int> cmpr_time;
int get_time_id(int x){ return lower_bound(cmpr_time.begin(),cmpr_time.end(),x)-cmpr_time.begin();}
const int M=2*N;
vector<int> lst[M],rst[M];
int ls[M],rs[M],tsz,root,lim,l_ptr[M],r_ptr[M];
void Build(int &c, int ss, int se, vector<int> l_segs, vector<int> r_segs)
{
c=++tsz;
vector<int> l_push[2],r_push[2];
int mid=ss+se>>1;
for(int i:l_segs)
{
if(tl[i]<=cmpr_time[ss] && tr[i]>=cmpr_time[se]) lst[c].pb(i);
else
{
if(tl[i]<=cmpr_time[mid]) l_push[0].pb(i);
if(tr[i]>=cmpr_time[mid+1]) l_push[1].pb(i);
}
}
for(int i:r_segs)
{
if(tl[i]<=cmpr_time[ss] && tr[i]>=cmpr_time[se]) rst[c].pb(i);
else
{
if(tl[i]<=cmpr_time[mid]) r_push[0].pb(i);
if(tr[i]>=cmpr_time[mid+1]) r_push[1].pb(i);
}
}
if(ss==se) return;
Build(ls[c],ss,mid,l_push[0],r_push[0]);
Build(rs[c],mid+1,se,l_push[1],r_push[1]);
}
int GetL(int c, int ss, int se, int id)
{
while(l_ptr[c]<lst[c].size() && r[lst[c][l_ptr[c]]]<qx[id]) l_ptr[c]++;
int ans=l_ptr[c]==lst[c].size()?0:qx[id]-l[lst[c][l_ptr[c]]];
if(ss==se) return ans;
int mid=ss+se>>1;
if(qt[id]<=cmpr_time[mid]) ans=max(ans,GetL(ls[c],ss,mid,id));
else ans=max(ans,GetL(rs[c],mid+1,se,id));
return ans;
}
int GetR(int c, int ss, int se, int id)
{
while(r_ptr[c]<rst[c].size() && l[rst[c][r_ptr[c]]]>qx[id]) r_ptr[c]++;
int ans=r_ptr[c]==rst[c].size()?0:r[rst[c][r_ptr[c]]]-qx[id];
if(ss==se) return ans;
int mid=ss+se>>1;
if(qt[id]<=cmpr_time[mid]) ans=max(ans,GetR(ls[c],ss,mid,id));
else ans=max(ans,GetR(rs[c],mid+1,se,id));
return ans;
}
int main()
{
scanf("%i %i %i",&n,&k,&q);
vector<pair<int,int>> events;
for(int i=1;i<=n;i++) scanf("%i %i %i %i",&x[i],&t[i],&a[i],&b[i]),events.pb({a[i],i}),events.pb({b[i]+1,-i});
for(int i=1;i<=q;i++) scanf("%i %i",&qx[i],&qt[i]),events.pb({qt[i],n+i}),cmpr_time.pb(qt[i]);
sort(cmpr_time.begin(),cmpr_time.end());
cmpr_time.resize(unique(cmpr_time.begin(),cmpr_time.end())-cmpr_time.begin());
sort(events.begin(),events.end());
for(int i=0;i<events.size();i++)
{
int id=events[i].second;
cur_time=events[i].first;
if(id<0) Del(-id);
else if(id<=n) Add(id);
else if(active!=k) ans[id-n]=-1;
}
for(int i=1;i<=hsz;i++) if(tr[i]==-1) tr[i]=cur_time;
vector<int> l_segs,r_segs;
l_segs.reserve(hsz);
r_segs.reserve(hsz);
for(int i=1;i<=hsz;i++) if(tl[i]<=tr[i]){ if(type[i]==l_type) l_segs.pb(i);else r_segs.pb(i);}
sort(l_segs.begin(),l_segs.end(),[&](int i, int j){ return l[i]<l[j];});
sort(r_segs.begin(),r_segs.end(),[&](int i, int j){ return r[i]>r[j];});
lim=(int)cmpr_time.size()-1;
Build(root,0,lim,l_segs,r_segs);
vector<int> qs;
for(int i=1;i<=q;i++) if(ans[i]!=-1) qs.pb(i);
sort(qs.begin(),qs.end(),[&](int i, int j){ return qx[i]<qx[j];});
for(int i:qs) ans[i]=GetL(root,0,lim,i);
reverse(qs.begin(),qs.end());
for(int i:qs) ans[i]=max(ans[i],GetR(root,0,lim,i));
for(int i=1;i<=q;i++) printf("%i\n",ans[i]);
return 0;
}