#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 60010
#define D 60010
ll n,q,k;
ll fans[N];
namespace Subtask3{
struct st{
ll col,typ,bef,aft;
double pnt;
bool operator<(const st&key)const{
if(this->pnt==key.pnt)return this->typ<key.typ;
return this->pnt<key.pnt;
}
};
vector<ll> xs[N];//色ごとの座標のset
bool aval[N];
vector<st> v;
multiset<ll> kei[2];
void init(){
rep(i,k)xs[i].clear();
rep(i,k)aval[i]=1;
v.clear();
rep(i,2)kei[i].clear();
}
void Ban(ll col){
aval[col]=0;
}
void pushN(ll t,ll x){
xs[t].push_back(x);
}
void pushQ(ll id,ll l){
v.push_back((struct st){-1,id,0,0,l});
}
int main(){
rep(i,k)if(aval[i])sort(xs[i].begin(),xs[i].end());
rep(i,2)kei[i].insert(-1e17);
rep(i,k)if(aval[i]){
if(xs[i].size()==0){
rep(j,2)kei[j].insert(1e17);
}
else{
kei[0].insert(xs[i][0]);
ll bef=xs[i][0];
rep(j,xs[i].size()-1){
v.push_back((struct st){i,1+2*j,bef,-xs[i][j],xs[i][j]}); bef=-xs[i][j];
v.push_back((struct st){i,2+2*j,bef,xs[i][j+1],(double)(xs[i][j+1]-xs[i][j])/2.0+xs[i][j]}); bef=xs[i][j+1];
}
v.push_back((struct st){i,1+2*(xs[i].size()-1),bef,-xs[i].back(),xs[i].back()});
}
}
sort(v.begin(),v.end());
for(auto e:v){
if(e.col<0){
ll ans=0;
chmax(ans,(ll){*kei[0].rbegin()-e.pnt});
chmax(ans,(ll){*kei[1].rbegin()+e.pnt});
chmax(fans[e.typ],ans);
}
else{
ll eo=e.typ%2;
kei[eo^1].erase(kei[eo^1].find(e.bef));
kei[eo^0].insert(e.aft);
}
}
}
}
multiset<ll> s[N];
struct st{
ll tim,x,col,typ;
bool operator<(const st&key)const{
if(this->tim==key.tim)return this->typ<key.typ;
return this->tim<key.tim;
}
};
ll x[N],col[N],a[N],b[N];
int main(){
cin>>n>>k>>q;
vector<st> v;
rep(i,n){
cin>>x[i]>>col[i]>>a[i]>>b[i]; col[i]--;
v.push_back((struct st){a[i],x[i],col[i],0});
v.push_back((struct st){b[i],x[i],col[i],2});
}
rep(i,q){
ll l,y; cin>>l>>y;
v.push_back((struct st){y,l,i,1});
fans[i]=0;
}
sort(v.begin(),v.end());
rep(i,k){
s[i].insert(-1);
s[i].insert(2e8);
}
unordered_set<ll> tyuui;
Subtask3::init();
rep(loops,v.size()){
auto e=v[loops];
if(e.typ==0){
Subtask3::Ban(e.col);
tyuui.insert(e.col);
}
if(e.typ==1){
Subtask3::pushQ(e.col,e.x);
}
if(e.typ==2){
Subtask3::Ban(e.col);
tyuui.insert(e.col);
}
if(loops%D==D-1||loops==v.size()-1){
rep(i,n){
if(!tyuui.count(col[i])){
bool vl=(struct st){a[i],x[i],col[i],0}<v[loops/D*D];
bool vr=v[loops]<(struct st){b[i],x[i],col[i],2};
if(vl&vr)Subtask3::pushN(col[i],x[i]);
}
}
//Subtask3::main();
for(ll j=loops/D*D;j<=loops;j++){
auto ee=v[j];
if(ee.typ==0){
s[ee.col].insert(ee.x);
}
if(ee.typ==1){
ll ans=0;
for(auto i:tyuui){
ll mi=1e17;
auto it=s[i].lower_bound(ee.x);
if(*it<2e8)chmin(mi,*it-ee.x);
it--;
if(*it>-1)chmin(mi,ee.x-*it);
chmax(ans,mi);
}
chmax(fans[ee.col],ans);
}
if(ee.typ==2){
s[ee.col].erase(s[ee.col].find(ee.x));
}
}
Subtask3::init();
tyuui.clear();
}
}
rep(i,q){
if(fans[i]>1e9)fans[i]=-1;
cout<<fans[i]<<endl;
}
}
Compilation message
new_home.cpp: In function 'void Subtask3::pushQ(ll, ll)':
new_home.cpp:41:37: warning: narrowing conversion of 'l' from 'll {aka long long int}' to 'double' inside { } [-Wnarrowing]
v.push_back((struct st){-1,id,0,0,l});
^
new_home.cpp: In function 'int Subtask3::main()':
new_home.cpp:8:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,n) for(int i=0;i<n;i++)
new_home.cpp:53:8:
rep(j,xs[i].size()-1){
~~~~~~~~~~~~~~~~
new_home.cpp:53:4: note: in expansion of macro 'rep'
rep(j,xs[i].size()-1){
^~~
new_home.cpp:54:59: warning: narrowing conversion of 'Subtask3::xs[i].std::vector<long long int>::operator[](((std::vector<long long int>::size_type)j))' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' to 'double' inside { } [-Wnarrowing]
v.push_back((struct st){i,1+2*j,bef,-xs[i][j],xs[i][j]}); bef=-xs[i][j];
^
new_home.cpp:57:31: warning: narrowing conversion of '(1 + (2 * (Subtask3::xs[i].std::vector<long long int>::size() - 1)))' from 'std::vector<long long int>::size_type {aka long unsigned int}' to 'll {aka long long int}' inside { } [-Wnarrowing]
v.push_back((struct st){i,1+2*(xs[i].size()-1),bef,-xs[i].back(),xs[i].back()});
~^~~~~~~~~~~~~~~~~~~
new_home.cpp:57:79: warning: narrowing conversion of 'Subtask3::xs[i].std::vector<long long int>::back()' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' to 'double' inside { } [-Wnarrowing]
v.push_back((struct st){i,1+2*(xs[i].size()-1),bef,-xs[i].back(),xs[i].back()});
~~~~~~~~~~^~
new_home.cpp:64:35: warning: narrowing conversion of '((double)(long long int)__builtin_memcpy(&<unnamed>, & Subtask3::kei[0].rbegin()()).std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >::operator*()() - e.Subtask3::st::pnt)' from 'double' to 'll {aka long long int}' inside { } [-Wnarrowing]
chmax(ans,(ll){*kei[0].rbegin()-e.pnt});
~~~~~~~~~~~~~~~~^~~~
new_home.cpp:10:28: note: in definition of macro 'chmax'
#define chmax(a,b) a=max(a,b)
^
new_home.cpp:65:35: warning: narrowing conversion of '((double)(long long int)__builtin_memcpy(&<unnamed>, & Subtask3::kei[1].rbegin()()).std::reverse_iterator<std::_Rb_tree_const_iterator<long long int> >::operator*()() + e.Subtask3::st::pnt)' from 'double' to 'll {aka long long int}' inside { } [-Wnarrowing]
chmax(ans,(ll){*kei[1].rbegin()+e.pnt});
~~~~~~~~~~~~~~~~^~~~
new_home.cpp:10:28: note: in definition of macro 'chmax'
#define chmax(a,b) a=max(a,b)
^
new_home.cpp:74:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
new_home.cpp: In function 'int main()':
new_home.cpp:8:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,n) for(int i=0;i<n;i++)
new_home.cpp:106:6:
rep(loops,v.size()){
~~~~~~~~~~~~~~
new_home.cpp:106:2: note: in expansion of macro 'rep'
rep(loops,v.size()){
^~~
new_home.cpp:120:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(loops%D==D-1||loops==v.size()-1){
~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
4600 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4600 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
4600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
4600 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4600 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
4600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
751 ms |
59032 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
748 ms |
56304 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
4600 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4600 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
4600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
4600 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4600 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
4600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
