/*
god taekyu
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define INF 210000000
#define OPEN 1
#define CLOSE 2
#define MAX 300005
int n,k,q;
struct query {
int idx,loc,year;
int ans;
};
struct store {
int loc,type,year,status;
};
query Q[MAX];
store A[MAX*2];
vector<int> LOC;
void input() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>k>>q;
for(int i=0;i<n;i++) {
int a,b,c,d;
cin>>a>>b>>c>>d;
a*=2;
A[2*i] = {a,b,c,OPEN};
A[2*i+1] = {a,b,d+1,CLOSE};
}
for(int i=0;i<q;i++) {
int a,b;
cin>>a>>b;
a*=2;
Q[i] = {i,a,b};
}
sort(A,A+2*n,[](store a,store b){return a.loc < b.loc;});
for(int i=0;i<2*n;i++) {
LOC.push_back(A[i].loc);
}
LOC.erase(unique(LOC.begin(),LOC.end()),LOC.end());
sort(A,A+2*n,[](store a,store b){return a.year < b.year;});
sort(Q,Q+q,[](query a,query b){return a.year < b.year;});
}
int T[MAX], T_filled = 0;
map<int,int> M[MAX]; //val, gaesu
int rightseg[4*MAX];//max
int leftseg[4*MAX]; //min
multiset<int> rightS[MAX];//max
multiset<int> leftS[MAX];//min
void updt(int seg[],int idx,int s,int e,int x,int v,int flag) {
if(s == e) {
seg[idx] = v;
return;
}
if(x<=(s+e)/2) {
updt(seg,idx*2,s,(s+e)/2,x,v,flag);
} else {
updt(seg,idx*2+1,(s+e)/2+1,e,x,v,flag);
}
if(flag == 0) {
seg[idx] = max(seg[idx*2] , seg[idx*2+1]);
} else {
seg[idx] = min(seg[idx*2] , seg[idx*2+1]);
}
}
void add_line(int bot,int top,int dir) {
int idx = lower_bound(LOC.begin(),LOC.end(),bot) - LOC.begin();
//cout<<"add : "<<bot<<" ~ "<<top<<'\n';
if(dir == 1) {
rightS[idx].insert(top);
multiset<int>::iterator it = rightS[idx].end(); it--;
updt(rightseg,1,0,n-1,idx,(*it),0);
} else {
leftS[idx].insert(top);
multiset<int>::iterator it = leftS[idx].begin();
updt(leftseg,1,0,n-1,idx,(*it),1);
}
}
void del_line(int bot,int top,int dir) {
//cout<<"del : "<<bot<<" ~ "<<top<<'\n';
int idx = lower_bound(LOC.begin(),LOC.end(),bot) - LOC.begin();
//cout<<"add : "<<bot<<" ~ "<<top<<'\n';
if(dir == 1) {
rightS[idx].erase(rightS[idx].find(top));
multiset<int>::iterator it = rightS[idx].end(); it--;
updt(rightseg,1,0,n-1,idx,(*it),0);
} else {
leftS[idx].erase(leftS[idx].find(top));
multiset<int>::iterator it = leftS[idx].begin();
updt(leftseg,1,0,n-1,idx,(*it),1);
}
}
void _add(int loc, int type) {
if(T[type] == 0) T_filled++;
T[type]++;
M[type][loc]++;
if(M[type][loc] == 1) {
map<int,int>::iterator it;
int rht=INF,lft=-1;
it = M[type].find(loc); it++;
if(it != M[type].end()) rht = (*it).first;
it = M[type].find(loc);
if(it != M[type].begin()) {it--;lft = (*it).first;}
if(rht == INF && lft == -1) {
add_line(loc,rht,1);
add_line(loc,lft,-1);
} else if(rht == INF) {
del_line(lft,INF,1);
add_line(lft,(lft+loc)/2,1);
add_line(loc,(lft+loc)/2,-1);
add_line(loc,rht,1);
} else if(lft == -1) {
del_line(rht,-1,-1);
add_line(rht,(loc+rht)/2,-1);
add_line(loc,(loc+rht)/2,1);
add_line(loc,lft,-1);
} else {
del_line(lft,(lft+rht)/2,1);
del_line(rht,(lft+rht)/2,-1);
add_line(loc,(loc+rht)/2,1);
add_line(loc,(loc+lft)/2,-1);
add_line(rht,(loc+rht)/2,-1);
add_line(lft,(loc+lft)/2,1);
}
}
}
void _del(int loc, int type) {
T[type]--;
if(T[type] == 0) T_filled--;
M[type][loc]--;
if(M[type][loc] == 0) {
map<int,int>::iterator it;
int rht=INF,lft=-1;
it = M[type].find(loc); it++;
if(it != M[type].end()) rht = (*it).first;
it = M[type].find(loc);
if(it != M[type].begin()) {it--;lft = (*it).first;}
if(rht == INF && lft == -1) {
del_line(loc,rht,1);
del_line(loc,lft,-1);
} else if(rht == INF) {
del_line(lft,(lft+loc)/2,1);
del_line(loc,(lft+loc)/2,-1);
del_line(loc,rht,1);
add_line(lft,INF,1);
} else if(lft == -1) {
del_line(rht,(loc+rht)/2,-1);
del_line(loc,(loc+rht)/2,1);
del_line(loc,lft,-1);
add_line(rht,-1,-1);
} else {
del_line(loc,(loc+rht)/2,1);
del_line(loc,(loc+lft)/2,-1);
del_line(rht,(loc+rht)/2,-1);
del_line(lft,(loc+lft)/2,1);
add_line(lft,(lft+rht)/2,1);
add_line(rht,(lft+rht)/2,-1);
}
M[type].erase(loc);
}
}
int leftquery(int idx,int s,int e,int v) {
if(leftseg[idx] > v) return -1;
if(s==e) {
if(leftseg[idx] <= v) return s;
return -1;
}
if(leftseg[idx*2+1] <= v) return leftquery(idx*2+1,(s+e)/2+1,e,v);
return leftquery(idx*2,s,(s+e)/2,v);
}
int rightquery(int idx,int s,int e,int v) {
if(rightseg[idx] < v) return INF;
if(s==e) {
if(rightseg[idx] >= v) return s;
return INF;
}
if(rightseg[idx*2] >= v) return rightquery(idx*2,s,(s+e)/2,v);
return rightquery(idx*2+1,(s+e)/2+1,e,v);
}
int main() {
input();
for(int i=0;i<n;i++) {
rightS[i].insert(-1);
updt(rightseg,1,0,n-1,i,-1,0);
leftS[i].insert(INF);
updt(leftseg,1,0,n-1,i,INF,1);
}
int Aidx = 0;
for(int i=0;i<q;i++) {
while(Aidx < 2*n && A[Aidx].year <= Q[i].year) {
if(A[Aidx].status == OPEN) {
_add(A[Aidx].loc, A[Aidx].type);
} else {
_del(A[Aidx].loc, A[Aidx].type);
}
Aidx++;
}
/*for(int j=4;j<=7;j++) {
cout<<rightseg[j]<<' ';
}
cout<<'\n';
for(int j=4;j<=7;j++) {
cout<<leftseg[j]<<' ';
}
cout<<"\n\n";*/
if(T_filled != k) {
Q[i].ans = -1;
//cout<<"-1\n";
} else {
int R = rightquery(1,0,n-1,Q[i].year);
int L = leftquery(1,0,n-1,Q[i].year);
//cout<<"ans : "<<LOC[R]<<' '<<LOC[L]<<'\n';
/*if(Q[i].loc > LOC[i] || Q[i].loc < LOC[R]) {
Q[i].ans = -1;
//cout<<"-1\n";
continue;
}*/
if(R == INF && L == -1) {
Q[i].ans = -1;
//cout<<"-1\n";
} else if(R == INF) {
Q[i].ans = (-Q[i].loc + LOC[L])/2;
} else if(L == -1) {
Q[i].ans = (-LOC[R] + Q[i].loc)/2;
} else {
Q[i].ans = max((-Q[i].loc + LOC[L])/2 , (-LOC[R] + Q[i].loc)/2);
}
}
}
sort(Q,Q+q,[](query a,query b){return a.idx < b.idx;});
for(int i=0;i<q;i++) {
cout<<Q[i].ans<<'\n';
}
return 0;
}
/*
god taekyu
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
42616 KB |
Output is correct |
| 2 |
Correct |
37 ms |
42852 KB |
Output is correct |
| 3 |
Correct |
40 ms |
42852 KB |
Output is correct |
| 4 |
Incorrect |
44 ms |
42852 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
42616 KB |
Output is correct |
| 2 |
Correct |
37 ms |
42852 KB |
Output is correct |
| 3 |
Correct |
40 ms |
42852 KB |
Output is correct |
| 4 |
Incorrect |
44 ms |
42852 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1680 ms |
140852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3492 ms |
140852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
42616 KB |
Output is correct |
| 2 |
Correct |
37 ms |
42852 KB |
Output is correct |
| 3 |
Correct |
40 ms |
42852 KB |
Output is correct |
| 4 |
Incorrect |
44 ms |
42852 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
42616 KB |
Output is correct |
| 2 |
Correct |
37 ms |
42852 KB |
Output is correct |
| 3 |
Correct |
40 ms |
42852 KB |
Output is correct |
| 4 |
Incorrect |
44 ms |
42852 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
