#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
struct fun{
int tl , tr , bound, x;
fun(){}
fun(int _tl , int _tr , int _bound , int _x){tl = _tl , tr = _tr , bound = _bound, x = _x;}
};
const int N = (int)6e2 + 10;
const int K = (int)3e2 + 10;
const int inf = 1e9;
const int M = (int)1e6 + 10;
set < pair < int , int > > pos[K];
vector < int > scanA[N], scanD[N], add[N], del[N];
int seg[4*M];
void upd(int v , int tl , int tr , int pos , int val){
if(tl == tr){
seg[v] = val;
return;
}
int mid = (tl + tr) >> 1 , v1 = v << 1;
if(pos <= mid)
upd(v1 , tl , mid , pos , val);
else
upd(v1 | 1 , mid + 1 , tr , pos , val);
seg[v] = min(seg[v1] , seg[v1|1]);
}
int get(int v , int tl , int tr , int l , int r){
if(tl == l && tr == r){
return seg[v];
}
int ans = inf, mid = (tl + tr) >> 1 , v1 = v << 1;
if(l <= mid)
ans = min(ans , get(v1, tl , mid , l , min(r , mid)));
if(r > mid)
ans = min(ans , get(v1 | 1 , mid + 1 , tr , max(l , mid + 1) , r));
return ans;
}
signed main(){
int n , q , k;
cin >> n >> k >> q;
vector < int > x(n), t(n), a(n), b(n);
vector < int > times, cords;
for(int i = 0 ; i < n; ++i){
cin >> x[i] >> t[i] >> a[i] >> b[i];
b[i]++;
times.push_back(a[i]), times.push_back(b[i]);
cords.push_back(x[i]);
}
vector < pair < int , int > > que(q);
for(auto &i : que){
cin >> i.fi >> i.se;
cords.push_back(i.fi);
times.push_back(i.se);
}
cords.pb(inf), cords.pb(-inf);
sort(all(times)), times.erase(unique(all(times)), times.end());
sort(all(cords)), cords.erase(unique(all(cords)), cords.end());
int Latest = inf;
vector < int > latest(k + 1 , -inf);
for(int i = 0 ; i < n; ++i){
x[i] = lower_bound(all(cords) , x[i]) - cords.begin();
a[i] = lower_bound(all(times) , a[i]) - times.begin();
b[i] = lower_bound(all(times) , b[i]) - times.begin();
add[a[i]].push_back(i);
del[b[i]].push_back(i);
latest[t[i]] = max(latest[t[i]], b[i]);
}
for(int t = 1; t <= k; ++t)
Latest= min(Latest ,latest[t]);
for(auto &i : que){
i.fi = lower_bound(all(cords), i.fi) - cords.begin();
i.se = lower_bound(all(times) , i.se) - times.begin();
}
/// first of all we should parse function R L
for(int i = 1; i <= k; ++i)
pos[i].insert({sz(cords)-1 , n}), pos[i].insert({0, n});
vector < fun > L, R;
vector < int > lstL(n + 1), lstR(n + 1);
for(int ti = 0; ti <= sz(times); ++ti){
for(auto &u : add[ti]){
int type = t[u];
auto it = pos[type].lower_bound(make_pair(x[u], -1));
auto it1 = it;
it1--;
/// how we change left and how we change right
int m = (cords[it->fi] + cords[it1->fi]) / 2;
if(lstL[it1->se] <= ti - 1){
L.push_back({lstL[it1->se], ti - 1, m, it1->fi});
lstL[it1->se] = ti;
}
lstL[it1->se] = ti;
if(lstR[it->se] <= ti - 1){
R.push_back({lstR[it->se], ti - 1, m, it->fi});
lstR[it->se] = ti;
}
lstR[it->se] = ti;
lstL[u] = ti;
lstR[u] = ti;
pos[type].insert(make_pair(x[u], u));
}
for(auto &u : del[ti]){
int type = t[u];
auto it = pos[type].lower_bound(make_pair(x[u], u));
auto it1 = it;
it1--;
auto it2 = it;
it2++;
if(lstR[it->se] <= ti - 1){
// assert(lstR[it1->se] >= lstL[it->se]);
int m1 = (cords[it->fi] + cords[it1->fi]) / 2;
R.push_back({lstR[it->se], ti - 1, m1, it->fi});
}
if(lstL[it->se] <= ti - 1){
// assert(lstR[it2->se] <= lstR[it2->se]);
int m2 = (cords[it->fi] + cords[it2->fi]) / 2;
L.push_back({lstL[it->se], ti - 1, m2, it->fi});
}
lstL[it1->se] = ti;
lstR[it2->se] = ti;
pos[type].erase(it);
}
}
vector < int > answer(q, inf);
vector < int > qperm(q);
vector < int > ans(q);
iota(all(qperm) , 0);
sort(all(qperm) , [&](int x , int y){
return que[x].se < que[y].se;
});
/// do scan LINE
// cout << " YO FUN \n";
// cout << "L \n";
// for(auto &u : L){
// cout << u.tl << ' ' << u.tr << ' ' << u.bound << ' ' << cords[u.x] << endl;
// }
//cout << "R \n";
// for(auto &u : R){
// cout << u.tl << ' ' << u.tr << ' ' << u.bound << ' ' << cords[u.x] << endl;
// }
// cout << endl;
//
// for(auto &u : que)
// cout << cords[u.fi] << ' ' << u.se << endl;
// cout << endl;
for(int i = 0; i < q; ++i){
assert(ans[i] == 0);
// cout << " LOL " << i << ' ' << que[i].se << endl;
for(auto &j : L){
if(j.tl <= que[i].se && j.tr >= que[i].se && que[i].fi <= j.bound){
ans[i] = max(ans[i] , cords[que[i].fi] - cords[j.x]);
}
}
for(auto &j : R){
if(j.tl <= que[i].se && j.tr >= que[i].se && que[i].fi >= j.bound){
ans[i] = max(ans[i] , -cords[que[i].fi] + cords[j.x]);
}
}
if(ans[i] >= (int)1e8 || que[i].se < Latest)
cout << ans[i] << '\n';
else
cout << -1 << '\n';
}
return 0;
if(false){
for(int i = 0; i < N; ++i){
scanA[i].clear();
scanD[i].clear();
}
/// so we gotta get them pos
vector < int > pos(sz(L));
iota(all(pos) , 0);
sort(all(pos) , [&](int x , int y){
return L[x].bound <= L[y].bound;
});
vector < int > revpos(sz(L));
for(int i = 0; i < sz(pos); ++i){
revpos[pos[i]] = i;
}
for(int i = 0; i < sz(pos); ++i){
scanA[L[i].tl].push_back(i);
scanD[R[i].tr + 1].push_back(i);
}
int lst = 0;
for(int tt = 0; tt < N; ++tt){
for(auto &u : scanA[tt]){
upd(1 , 0 , M - 1 , revpos[u], L[u].x);
}
for(auto &u : scanD[tt]){
upd(1 , 0 , M - 1 , revpos[u], inf);
}
while(lst < q && que[qperm[lst]].se == tt){
int f = qperm[lst];
int l = 0 , r = sz(L) - 1;
while(l != r){
int mid = (l + r) >> 1;
if(cords[que[f].fi] <= L[mid].bound){
if(l + 1 == r)
l = r;
else
l = mid;
}else
r = mid;
}
if(cords[que[f].fi] <= L[r].bound)
++r;
--r;
/// so what do we say we say that suffix is GOOOD
int tv;
if(r == -1)
tv = inf;
else
tv = get(1 , 0, M-1, r , sz(L) - 1);
if(tv == inf)
tv = inf;
else
tv = cords[tv];
ans[f] = max(ans[f] , cords[que[f].fi] - tv);
lst++;
}
}
}
if(false){
for(int i = 0; i < N; ++i){
scanA[i].clear();
scanD[i].clear();
}
/// so we gotta get them pos
vector < int > pos(sz(R));
iota(all(pos) , 0);
sort(all(pos) , [&](int x , int y){
return R[x].bound <= R[y].bound;
});
vector < int > revpos(sz(R));
for(int i = 0; i < sz(pos); ++i){
revpos[pos[i]] = i;
}
for(int i = 0; i < sz(pos); ++i){
scanA[R[i].tl].push_back(i);
scanD[R[i].tr + 1].push_back(i);
}
int lst = 0;
for(int tt = 0; tt < N; ++tt){
for(auto &u : scanA[tt]){
upd(1 , 0 , M - 1 , revpos[u], -R[u].x);
}
for(auto &u : scanD[tt]){
upd(1 , 0 , M - 1 , revpos[u], inf);
}
while(lst < q && que[qperm[lst]].se == tt){
int f = qperm[lst];
int l = 0 , r = sz(R) - 1;
while(l != r){
int mid = (l + r) >> 1;
if(cords[que[f].fi] <= R[mid].bound){
if(l + 1 == r)
l = r;
else
l = mid;
}else
r = mid;
}
if(cords[que[f].fi] <= R[r].bound)
++r;
--r;
/// so what do we say we say that suffix is GOOOD
int tv;
if(r == -1)
tv = inf;
else
tv = get(1 , 0, M-1, 0 , r);
if(tv == inf)
tv = inf;
else
tv = cords[tv];
tv *= -1;
ans[f] = max(ans[f] , tv - cords[que[f].fi]);
lst++;
}
}
}
for(int i = 0 ; i < q; ++i){
if(ans[i] >= (int)1e8)
cout << -1 << '\n';
else
cout << ans[i] << '\n';
}
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1 1
1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
642 ms |
32228 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
640 ms |
34972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
