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=2e7;
const int INF=1e8;
struct data
{
int val;
int left;
int right;
} seg[MAX],seg_[MAX];
multiset<int> st[MAX];
multiset<int> itr it,nxt,pre;
vector<int> vec[MAX];
vector<pii> order;
vector< pair<int,pii> > ask;
int N,K,Q,X,Y,n,t,timer,timers,ptr,type[MAX],loc[MAX],res[MAX];
int get(int X,int Y)
{
return Y-X;
}
int gets(int X,int Y)
{
if(!Y)
return 0;
return X-Y;
}
void UpdateNeg(int low,int high,int node,int qlow,int delta)
{
if(low>high or qlow>high)
return ;
if(qlow<=low)
{
seg[node].val=max(seg[node].val,delta);
return ;
}
if(!seg[node].left)
seg[node].left=++timer;
if(!seg[node].right)
seg[node].right=++timer;
int mid=(low+high)/2;
UpdateNeg(low,mid,seg[node].left,qlow,delta);
UpdateNeg(mid+1,high,seg[node].right,qlow,delta);
return ;
}
void UpdatePos(int low,int high,int node,int qhigh,int delta)
{
if(low>high or low>qhigh)
return ;
if(high<=qhigh)
{
if(!seg_[node].val)
seg_[node].val=delta;
else
seg_[node].val=min(seg_[node].val,delta);
return ;
}
if(!seg_[node].left)
seg_[node].left=++timers;
if(!seg_[node].right)
seg_[node].right=++timers;
int mid=(low+high)/2;
UpdatePos(low,mid,seg_[node].left,qhigh,delta);
UpdatePos(mid+1,high,seg_[node].right,qhigh,delta);
return ;
}
int QueryNeg(int low,int high,int node,int idx)
{
if(!node)
return 0;
if(low==high)
return get(idx,seg[node].val);
int mid=(low+high)/2;
if(idx>=low and idx<=mid)
return max(get(idx,seg[node].val),QueryNeg(low,mid,seg[node].left,idx));
else
return max(get(idx,seg[node].val),QueryNeg(mid+1,high,seg[node].right,idx));
}
int QueryPos(int low,int high,int node,int idx)
{
if(!node)
return 0;
if(low==high)
return gets(idx,seg_[node].val);
int mid=(low+high)/2;
if(idx>=low and idx<=mid)
return max(gets(idx,seg_[node].val),QueryPos(low,mid,seg_[node].left,idx));
else
return max(gets(idx,seg_[node].val),QueryPos(mid+1,high,seg_[node].right,idx));
}
void exclude(int ind)
{
int CurType=type[ind],CurLoc=loc[ind];
it=st[CurType].find(CurLoc);
if(it==st[CurType].end())
{
while(true)
it++;
}
if(it==st[CurType].begin())
{
if((++it)==st[CurType].end())
{
UpdateNeg(1,n,1,1,INF+99);
st[CurType].erase(--it);
return ;
}
--it;
}
if(it==st[CurType].begin())
{
nxt=it;
++nxt;
UpdateNeg(1,n,1,1,*nxt);
st[CurType].erase(it);
}
else if((++it)==st[CurType].end())
{
--it;
pre=it;
--pre;
UpdatePos(1,n,1,n,*pre);
st[CurType].erase(it);
}
else
{
--it;
pre=it;
nxt=it;
--pre;
++nxt;
UpdatePos(1,n,1,(*pre+*nxt)/2,*pre);
UpdateNeg(1,n,1,(*pre+*nxt+1)/2,*nxt);
st[CurType].erase(it);
}
return ;
}
signed main()
{
ios_base::sync_with_stdio(false);
n=INF;
timer=1;
timers=1;
cin>>N>>K>>Q;
for(int A=1;A<=N;A++)
{
cin>>loc[A]>>type[A]>>X>>X;
vec[type[A]].pb(loc[A]);
st[type[A]].insert(loc[A]);
order.pb(mp(X,A));
}
sort(order.begin(),order.end());
for(int A=1;A<=K;A++)
{
if(vec[A].empty())
{
while(Q--)
cout<<-1<<"\n";
return 0;
}
sort(vec[A].begin(),vec[A].end());
for(int B=1;B<vec[A].size();B++)
UpdateNeg(1,n,1,(vec[A][B]+vec[A][B-1]+1)/2,vec[A][B]);
for(int B=0;B<vec[A].size()-1;B++)
UpdatePos(1,n,1,(vec[A][B]+vec[A][B+1])/2,vec[A][B]);
UpdateNeg(1,n,1,1,*vec[A].begin());
UpdatePos(1,n,1,n,vec[A].back());
}
for(int A=1;A<=Q;A++)
{
cin>>X>>Y;
ask.pb(mp(Y,mp(X,A)));
}
sort(ask.begin(),ask.end());
for(auto A:ask)
{
while(ptr<order.size() and order[ptr].first<A.first)
{
exclude(order[ptr].second);
++ptr;
}
res[A.second.second]=max(QueryPos(1,n,1,A.second.first),QueryNeg(1,n,1,A.second.first));
}
for(int A=1;A<=Q;A++)
{
if(res[A]>=INF)
res[A]=-1;
cout<<res[A]<<"\n";
}
return 0;
}
Compilation message (stderr)
new_home.cpp: In function 'int main()':
new_home.cpp:184:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int B=1;B<vec[A].size();B++)
~^~~~~~~~~~~~~~
new_home.cpp:186:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int B=0;B<vec[A].size()-1;B++)
~^~~~~~~~~~~~~~~~
new_home.cpp:199:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ptr<order.size() and order[ptr].first<A.first)
~~~^~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::(anonymous namespace)::__destroy_string<wchar_t>(void*)':
(.text._ZNSt13__facet_shims12_GLOBAL__N_116__destroy_stringIwEEvPv+0x1e): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::(anonymous namespace)::__destroy_string<char>(void*)':
(.text._ZNSt13__facet_shims12_GLOBAL__N_116__destroy_stringIcEEvPv+0x1e): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<wchar_t>::do_get(std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, bool, std::ios_base&, std::_Ios_Iostate&, std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIwE6do_getESt19istreambuf_iteratorIwSt11char_traitsIwEES6_bRSt8ios_baseRSt12_Ios_IostateRSbIwS5_SaIwEE+0xfe): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<wchar_t>::do_get(std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, bool, std::ios_base&, std::_Ios_Iostate&, std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIwE6do_getESt19istreambuf_iteratorIwSt11char_traitsIwEES6_bRSt8ios_baseRSt12_Ios_IostateRSbIwS5_SaIwEE+0x17b): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<char>::do_get(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, bool, std::ios_base&, std::_Ios_Iostate&, std::string&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIcE6do_getESt19istreambuf_iteratorIcSt11char_traitsIcEES6_bRSt8ios_baseRSt12_Ios_IostateRSs+0xfe): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<char>::do_get(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, bool, std::ios_base&, std::_Ios_Iostate&, std::string&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIcE6do_getESt19istreambuf_iteratorIcSt11char_traitsIcEES6_bRSt8ios_baseRSt12_Ios_IostateRSs+0x17b): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<char>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<char>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0xa1): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<char>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<char>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x24f): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0xa9): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x114): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x294): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status