#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<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;
vp[i].fs.sc--;
g.push_back({vp[i].fs.fs,vp[i].fs.sc});
}
sort(g.begin(),g.end());
vector<pii> sl;
vector<int> s(k,-1);
multiset<int> ms;
vector<pair<int,pii> > eve;
for(auto h:g){
if(s[h.sc]==-1){
ms.insert(h.fs);
}
else{
eve.push_back({(s[h.sc]+h.fs+1)/2,{s[h.sc],h.fs}});
}
s[h.sc]=h.fs;
}
for(int i=0;i<k;i++){
if(s[i]==-1){
for(int j=0;j<q;j++){
cout << -1 << "\n";
}
return 0;
}
}
vector<int> ans(q+1);
for(int i=1;i<=q;i++){
int l,y;
cin >> l >> y;
eve.push_back({l,{-1,i}});
}
sort(eve.begin(),eve.end());
vector<pii> ins,que;
int nw=-1;
for(auto t:eve){
if(t.fs!=nw){
for(auto h:ins){
ms.erase(ms.find(h.fs));
ms.insert(h.sc);
}
for(auto h:que){
auto y=*ms.rbegin();
auto z=*ms.begin();
ans[h.sc]=max(abs(y-h.fs),abs(z-h.fs));
}
ins.clear();
que.clear();
}
if(t.sc.fs<0){
que.push_back({t.fs,t.sc.sc});
}
else{
ins.push_back(t.sc);
}
nw=t.fs;
}
for(auto h:ins){
ms.erase(ms.find(h.fs));
ms.insert(h.sc);
}
for(auto h:que){
auto y=*ms.rbegin();
auto z=*ms.begin();
ans[h.sc]=max(abs(y-h.fs),abs(z-h.fs));
}
for(int i=1;i<=q;i++){
cout << ans[i] << "\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
447 ms |
48024 KB |
Output is correct |
2 |
Correct |
319 ms |
56548 KB |
Output is correct |
3 |
Correct |
342 ms |
65108 KB |
Output is correct |
4 |
Correct |
403 ms |
51740 KB |
Output is correct |
5 |
Correct |
282 ms |
56552 KB |
Output is correct |
6 |
Correct |
326 ms |
56512 KB |
Output is correct |
7 |
Correct |
323 ms |
65072 KB |
Output is correct |
8 |
Correct |
442 ms |
51952 KB |
Output is correct |
9 |
Correct |
421 ms |
59008 KB |
Output is correct |
10 |
Correct |
353 ms |
57084 KB |
Output is correct |
11 |
Correct |
354 ms |
56336 KB |
Output is correct |
12 |
Correct |
334 ms |
56780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
365 ms |
46048 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |