#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
typedef pair<int,int> pii;
signed main(){
AquA;
int n,k,q;
cin >> n >> k >> q;
vector<pair<pii,pii> > vp(n);
vector<pair<int,pii> > g;
for(int i=0;i<n;i++){
cin >> vp[i].fs.fs >> vp[i].fs.sc >> vp[i].sc.fs >> vp[i].sc.sc;
g.push_back({vp[i].sc.fs,vp[i].fs});
g.push_back({vp[i].sc.sc,{vp[i].fs.fs,-vp[i].fs.sc}});
}
vector<multiset<int> > s(k);
for(int i=0;i<k;i++){
s[i].insert(-2e9);
s[i].insert(2e9);
}
vector<int> ans(q+1);
for(int i=1;i<=q;i++){
int l,y;
cin >> l >> y;
g.push_back({y,{-i,l}});
}
sort(g.begin(),g.end());
vector<pii> ins,que,de;
int nw=-1;
for(auto t:g){
if(t.fs!=nw){
for(auto h:ins){
s[h.sc-1].insert(h.fs);
}
for(auto h:que){
for(int i=0;i<k;i++){
auto y=s[i].lower_bound(h.sc);
auto z=prev(y);
ans[-h.fs]=max(ans[-h.fs],min((*y)-h.sc,h.sc-(*z)));
}
}
for(auto h:de){
s[(-h.sc)-1].erase(s[-h.sc].find(h.fs));
}
ins.clear();
que.clear();
de.clear();
}
if(t.sc.fs<0){
que.push_back(t.sc);
}
else if(t.sc.sc<0){
de.push_back(t.sc);
}
else{
ins.push_back(t.sc);
}
nw=t.fs;
}
for(auto h:ins){
s[h.sc].insert(h.fs);
}
for(auto h:que){
for(int i=0;i<k;i++){
auto y=s[i].lower_bound(h.sc);
auto z=prev(y);
ans[-h.fs]=max(ans[-h.fs],min((*y)-h.sc,h.sc-(*z)));
}
}
for(auto h:de){
s[-h.sc].erase(s[-h.sc].find(h.fs));
}
for(int i=1;i<=q;i++){
if(ans[i]>1e9){
cout << -1 << "\n";
}
else{
cout << ans[i] << "\n";
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
5037 ms |
60404 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
378 ms |
106928 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |