#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef priority_queue<pii> max_heap;
typedef priority_queue<pii, vector<pii>, greater<pii>> min_heap;
const int MX=300010, inf=2e9;
struct SHOP {
int x, type, s, e, idx;
} S[MX];
struct QUERY {
int x, t, idx, ans;
} Q[MX];
int n, q, k;
void input(){
cin>>n>>k>>q;
for(int i=1; i<=n; i++){
int t, x, s, e;
cin>>x>>t>>s>>e;
S[i]={x,t,s,e,i};
}
for(int i=1; i<=q; i++){
int x, t;
cin>>x>>t;
Q[i]={x,t,i};
}
}
void prec(){
for(int i=1; i<=n; i++){
S[i].x*=2;
}
for(int i=1; i<=q; i++){
Q[i].x*=2;
}
// 좌표압축
}
//////
multiset<int> pos[MX];
// seg
multiset<pii> A, B; // A가 /, B가 \
void add(int x1, int x2){
int mx=(0LL+x1+x2)/2, my=(0LL+x2-x1)/2;
pii p=pii(mx, my);
A.insert(p);
B.insert(p);
}
void del(int x1, int x2){
int mx=(0LL+x1+x2)/2, my=(0LL+x2-x1)/2;
pii p=pii(mx, my);
A.erase(A.find(p));
B.erase(B.find(p));
}
void add_store(int idx){
// cout<<"ADD: "<<idx<<'\n';
// 지금 샵 : S[idx];
// 지금 셋 : pos[S[idx].type]
multiset<int> &stores = pos[S[idx].type];
int x=S[idx].x;
if(stores.find(x)!=stores.end()){
stores.insert(x);
return;
}
auto it1=stores.lower_bound(x);
auto it2=stores.lower_bound(x); it2--;
int lx=*it2, rx=*it1;
del(lx, rx);
add(lx, x); add(x, rx);
stores.insert(x);
}
void del_store(int idx){
// cout<<"DEL: "<<idx<<'\n';
multiset<int> &stores = pos[S[idx].type];
int x=S[idx].x;
if(stores.find(x)==stores.end()){
return;
}
stores.erase(stores.find(x));
if(stores.find(x)!=stores.end()){
return;
}
auto it1=stores.lower_bound(x);
auto it2=stores.lower_bound(x); it2--;
int lx=*it2, rx=*it1;
del(lx, x); del(x, rx);
add(lx, rx);
}
void init(){
// seg 초기화?
for(int i=1; i<=k; i++){
pos[i].insert(inf);
pos[i].insert(-inf);
add(-inf, inf);
}
}
////
void debug(){
cout<<"\nDEBUG...\n";
for(int i=1; i<=k; i++){
for(auto p:pos[i])
cout<<p<<' ';
cout<<'\n';
}
cout<<'\n';
}
int find(int qx){
int ans=-inf;
// debug();
for(pii p:A){
int x, y; tie(x,y)=p;
if(x<qx) continue;
ans=max(ans, y-x+qx);
}
for(pii p:B){
int x, y; tie(x,y)=p;
if(x>qx) continue;
ans=max(ans, y+x-qx);
}
return ans;
}
void solve(){
min_heap in, out;
for(int i=1; i<=n; i++){
in.push({S[i].s, i});
out.push({S[i].e, i});
}
sort(Q+1, Q+q+1, [](QUERY &a, QUERY &b){ return a.t<b.t; });
init();
for(int i=1; i<=q; i++){
int qt=Q[i].t, qx=Q[i].x;
while(!in.empty()){
int t,idx; tie(t,idx)=in.top();
if(qt<t) break;
in.pop();
add_store(idx);
}
while(!out.empty()){
int t,idx; tie(t,idx)=out.top();
if(qt<=t) break;
out.pop();
del_store(idx);
}
Q[i].ans=find(qx);
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
input();
prec();
solve();
sort(Q+1, Q+n+1, [](QUERY &a, QUERY &b){ return a.idx<b.idx; });
for(int i=1; i<=q; i++){
cout<<(Q[i].ans>inf/3 ? -1 : Q[i].ans/2)<<'\n';
}
return 0;
}
Compilation message
new_home.cpp:48:21: warning: multi-line comment [-Wcomment]
multiset<pii> A, B; // A가 /, B가 \
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
14456 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
14456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
14456 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
14456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5052 ms |
83332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5027 ms |
83332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
14456 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
14456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
14456 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
14456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
