#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 4000
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;
cin.tie(0);
ios::sync_with_stdio(0);
vector<st> v;
bool thcol[N];
rep(i,k)thcol[i]=0;
rep(i,n){
cin>>x[i]>>col[i]>>a[i]>>b[i]; col[i]--;
thcol[col[i]]=1;
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;
}
bool ok=1;
rep(i,k)ok&=thcol[i];
if(ok==0){
rep(i,q)cout<<-1<<"\n";
return 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]<<"\n";
}
}
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:117:6:
rep(loops,v.size()){
~~~~~~~~~~~~~~
new_home.cpp:117:2: note: in expansion of macro 'rep'
rep(loops,v.size()){
^~~
new_home.cpp:131: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 |
Correct |
7 ms |
4600 KB |
Output is correct |
4 |
Correct |
7 ms |
4600 KB |
Output is correct |
5 |
Correct |
8 ms |
4728 KB |
Output is correct |
6 |
Correct |
7 ms |
4728 KB |
Output is correct |
7 |
Correct |
10 ms |
4728 KB |
Output is correct |
8 |
Correct |
9 ms |
4728 KB |
Output is correct |
9 |
Correct |
10 ms |
4732 KB |
Output is correct |
10 |
Correct |
8 ms |
4728 KB |
Output is correct |
11 |
Correct |
8 ms |
4728 KB |
Output is correct |
12 |
Correct |
8 ms |
4728 KB |
Output is correct |
13 |
Correct |
8 ms |
4728 KB |
Output is correct |
14 |
Correct |
8 ms |
4732 KB |
Output is correct |
15 |
Correct |
10 ms |
4728 KB |
Output is correct |
16 |
Correct |
9 ms |
4728 KB |
Output is correct |
17 |
Correct |
8 ms |
4728 KB |
Output is correct |
18 |
Correct |
9 ms |
4728 KB |
Output is correct |
19 |
Correct |
9 ms |
4728 KB |
Output is correct |
20 |
Correct |
9 ms |
4728 KB |
Output is correct |
21 |
Correct |
10 ms |
4728 KB |
Output is correct |
22 |
Correct |
11 ms |
4728 KB |
Output is correct |
23 |
Correct |
9 ms |
4728 KB |
Output is correct |
24 |
Correct |
10 ms |
4728 KB |
Output is correct |
25 |
Correct |
8 ms |
4728 KB |
Output is correct |
26 |
Correct |
8 ms |
4732 KB |
Output is correct |
27 |
Correct |
8 ms |
4728 KB |
Output is correct |
28 |
Correct |
8 ms |
4732 KB |
Output is correct |
29 |
Correct |
8 ms |
4728 KB |
Output is correct |
30 |
Correct |
7 ms |
4728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
4600 KB |
Output is correct |
2 |
Correct |
7 ms |
4600 KB |
Output is correct |
3 |
Correct |
7 ms |
4600 KB |
Output is correct |
4 |
Correct |
7 ms |
4600 KB |
Output is correct |
5 |
Correct |
8 ms |
4728 KB |
Output is correct |
6 |
Correct |
7 ms |
4728 KB |
Output is correct |
7 |
Correct |
10 ms |
4728 KB |
Output is correct |
8 |
Correct |
9 ms |
4728 KB |
Output is correct |
9 |
Correct |
10 ms |
4732 KB |
Output is correct |
10 |
Correct |
8 ms |
4728 KB |
Output is correct |
11 |
Correct |
8 ms |
4728 KB |
Output is correct |
12 |
Correct |
8 ms |
4728 KB |
Output is correct |
13 |
Correct |
8 ms |
4728 KB |
Output is correct |
14 |
Correct |
8 ms |
4732 KB |
Output is correct |
15 |
Correct |
10 ms |
4728 KB |
Output is correct |
16 |
Correct |
9 ms |
4728 KB |
Output is correct |
17 |
Correct |
8 ms |
4728 KB |
Output is correct |
18 |
Correct |
9 ms |
4728 KB |
Output is correct |
19 |
Correct |
9 ms |
4728 KB |
Output is correct |
20 |
Correct |
9 ms |
4728 KB |
Output is correct |
21 |
Correct |
10 ms |
4728 KB |
Output is correct |
22 |
Correct |
11 ms |
4728 KB |
Output is correct |
23 |
Correct |
9 ms |
4728 KB |
Output is correct |
24 |
Correct |
10 ms |
4728 KB |
Output is correct |
25 |
Correct |
8 ms |
4728 KB |
Output is correct |
26 |
Correct |
8 ms |
4732 KB |
Output is correct |
27 |
Correct |
8 ms |
4728 KB |
Output is correct |
28 |
Correct |
8 ms |
4732 KB |
Output is correct |
29 |
Correct |
8 ms |
4728 KB |
Output is correct |
30 |
Correct |
7 ms |
4728 KB |
Output is correct |
31 |
Correct |
2463 ms |
16080 KB |
Output is correct |
32 |
Correct |
148 ms |
14944 KB |
Output is correct |
33 |
Correct |
239 ms |
14944 KB |
Output is correct |
34 |
Correct |
1991 ms |
14944 KB |
Output is correct |
35 |
Correct |
1103 ms |
16052 KB |
Output is correct |
36 |
Correct |
288 ms |
16092 KB |
Output is correct |
37 |
Correct |
233 ms |
14944 KB |
Output is correct |
38 |
Correct |
168 ms |
14948 KB |
Output is correct |
39 |
Correct |
156 ms |
14944 KB |
Output is correct |
40 |
Correct |
151 ms |
14944 KB |
Output is correct |
41 |
Correct |
528 ms |
14944 KB |
Output is correct |
42 |
Correct |
663 ms |
14944 KB |
Output is correct |
43 |
Correct |
456 ms |
26752 KB |
Output is correct |
44 |
Correct |
436 ms |
14948 KB |
Output is correct |
45 |
Correct |
208 ms |
14944 KB |
Output is correct |
46 |
Correct |
133 ms |
14944 KB |
Output is correct |
47 |
Correct |
132 ms |
14816 KB |
Output is correct |
48 |
Correct |
124 ms |
14816 KB |
Output is correct |
49 |
Correct |
148 ms |
14820 KB |
Output is correct |
50 |
Correct |
420 ms |
14944 KB |
Output is correct |
51 |
Correct |
135 ms |
14944 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
257 ms |
56504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
288 ms |
55952 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 |
Correct |
7 ms |
4600 KB |
Output is correct |
4 |
Correct |
7 ms |
4600 KB |
Output is correct |
5 |
Correct |
8 ms |
4728 KB |
Output is correct |
6 |
Correct |
7 ms |
4728 KB |
Output is correct |
7 |
Correct |
10 ms |
4728 KB |
Output is correct |
8 |
Correct |
9 ms |
4728 KB |
Output is correct |
9 |
Correct |
10 ms |
4732 KB |
Output is correct |
10 |
Correct |
8 ms |
4728 KB |
Output is correct |
11 |
Correct |
8 ms |
4728 KB |
Output is correct |
12 |
Correct |
8 ms |
4728 KB |
Output is correct |
13 |
Correct |
8 ms |
4728 KB |
Output is correct |
14 |
Correct |
8 ms |
4732 KB |
Output is correct |
15 |
Correct |
10 ms |
4728 KB |
Output is correct |
16 |
Correct |
9 ms |
4728 KB |
Output is correct |
17 |
Correct |
8 ms |
4728 KB |
Output is correct |
18 |
Correct |
9 ms |
4728 KB |
Output is correct |
19 |
Correct |
9 ms |
4728 KB |
Output is correct |
20 |
Correct |
9 ms |
4728 KB |
Output is correct |
21 |
Correct |
10 ms |
4728 KB |
Output is correct |
22 |
Correct |
11 ms |
4728 KB |
Output is correct |
23 |
Correct |
9 ms |
4728 KB |
Output is correct |
24 |
Correct |
10 ms |
4728 KB |
Output is correct |
25 |
Correct |
8 ms |
4728 KB |
Output is correct |
26 |
Correct |
8 ms |
4732 KB |
Output is correct |
27 |
Correct |
8 ms |
4728 KB |
Output is correct |
28 |
Correct |
8 ms |
4732 KB |
Output is correct |
29 |
Correct |
8 ms |
4728 KB |
Output is correct |
30 |
Correct |
7 ms |
4728 KB |
Output is correct |
31 |
Correct |
2463 ms |
16080 KB |
Output is correct |
32 |
Correct |
148 ms |
14944 KB |
Output is correct |
33 |
Correct |
239 ms |
14944 KB |
Output is correct |
34 |
Correct |
1991 ms |
14944 KB |
Output is correct |
35 |
Correct |
1103 ms |
16052 KB |
Output is correct |
36 |
Correct |
288 ms |
16092 KB |
Output is correct |
37 |
Correct |
233 ms |
14944 KB |
Output is correct |
38 |
Correct |
168 ms |
14948 KB |
Output is correct |
39 |
Correct |
156 ms |
14944 KB |
Output is correct |
40 |
Correct |
151 ms |
14944 KB |
Output is correct |
41 |
Correct |
528 ms |
14944 KB |
Output is correct |
42 |
Correct |
663 ms |
14944 KB |
Output is correct |
43 |
Correct |
456 ms |
26752 KB |
Output is correct |
44 |
Correct |
436 ms |
14948 KB |
Output is correct |
45 |
Correct |
208 ms |
14944 KB |
Output is correct |
46 |
Correct |
133 ms |
14944 KB |
Output is correct |
47 |
Correct |
132 ms |
14816 KB |
Output is correct |
48 |
Correct |
124 ms |
14816 KB |
Output is correct |
49 |
Correct |
148 ms |
14820 KB |
Output is correct |
50 |
Correct |
420 ms |
14944 KB |
Output is correct |
51 |
Correct |
135 ms |
14944 KB |
Output is correct |
52 |
Execution timed out |
5062 ms |
28840 KB |
Time limit exceeded |
53 |
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 |
Correct |
7 ms |
4600 KB |
Output is correct |
4 |
Correct |
7 ms |
4600 KB |
Output is correct |
5 |
Correct |
8 ms |
4728 KB |
Output is correct |
6 |
Correct |
7 ms |
4728 KB |
Output is correct |
7 |
Correct |
10 ms |
4728 KB |
Output is correct |
8 |
Correct |
9 ms |
4728 KB |
Output is correct |
9 |
Correct |
10 ms |
4732 KB |
Output is correct |
10 |
Correct |
8 ms |
4728 KB |
Output is correct |
11 |
Correct |
8 ms |
4728 KB |
Output is correct |
12 |
Correct |
8 ms |
4728 KB |
Output is correct |
13 |
Correct |
8 ms |
4728 KB |
Output is correct |
14 |
Correct |
8 ms |
4732 KB |
Output is correct |
15 |
Correct |
10 ms |
4728 KB |
Output is correct |
16 |
Correct |
9 ms |
4728 KB |
Output is correct |
17 |
Correct |
8 ms |
4728 KB |
Output is correct |
18 |
Correct |
9 ms |
4728 KB |
Output is correct |
19 |
Correct |
9 ms |
4728 KB |
Output is correct |
20 |
Correct |
9 ms |
4728 KB |
Output is correct |
21 |
Correct |
10 ms |
4728 KB |
Output is correct |
22 |
Correct |
11 ms |
4728 KB |
Output is correct |
23 |
Correct |
9 ms |
4728 KB |
Output is correct |
24 |
Correct |
10 ms |
4728 KB |
Output is correct |
25 |
Correct |
8 ms |
4728 KB |
Output is correct |
26 |
Correct |
8 ms |
4732 KB |
Output is correct |
27 |
Correct |
8 ms |
4728 KB |
Output is correct |
28 |
Correct |
8 ms |
4732 KB |
Output is correct |
29 |
Correct |
8 ms |
4728 KB |
Output is correct |
30 |
Correct |
7 ms |
4728 KB |
Output is correct |
31 |
Correct |
2463 ms |
16080 KB |
Output is correct |
32 |
Correct |
148 ms |
14944 KB |
Output is correct |
33 |
Correct |
239 ms |
14944 KB |
Output is correct |
34 |
Correct |
1991 ms |
14944 KB |
Output is correct |
35 |
Correct |
1103 ms |
16052 KB |
Output is correct |
36 |
Correct |
288 ms |
16092 KB |
Output is correct |
37 |
Correct |
233 ms |
14944 KB |
Output is correct |
38 |
Correct |
168 ms |
14948 KB |
Output is correct |
39 |
Correct |
156 ms |
14944 KB |
Output is correct |
40 |
Correct |
151 ms |
14944 KB |
Output is correct |
41 |
Correct |
528 ms |
14944 KB |
Output is correct |
42 |
Correct |
663 ms |
14944 KB |
Output is correct |
43 |
Correct |
456 ms |
26752 KB |
Output is correct |
44 |
Correct |
436 ms |
14948 KB |
Output is correct |
45 |
Correct |
208 ms |
14944 KB |
Output is correct |
46 |
Correct |
133 ms |
14944 KB |
Output is correct |
47 |
Correct |
132 ms |
14816 KB |
Output is correct |
48 |
Correct |
124 ms |
14816 KB |
Output is correct |
49 |
Correct |
148 ms |
14820 KB |
Output is correct |
50 |
Correct |
420 ms |
14944 KB |
Output is correct |
51 |
Correct |
135 ms |
14944 KB |
Output is correct |
52 |
Runtime error |
257 ms |
56504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
53 |
Halted |
0 ms |
0 KB |
- |