#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
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 >> q >> k;
vector < int > x(n), t(n), a(n), b(n);
vector < int > times, cords;
for(int i = 0 ; i < n; ++i){
cin >> t[i] >> x[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);
}
sort(all(times)), times.erase(unique(all(times)), times.end());
sort(all(cords)), cords.erase(unique(all(cords)), cords.end());
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) , a[i]) - times.begin();
add[a[i]].push_back(i);
del[b[i] + 1].push_back(i);
}
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({-inf , n}), pos[i].insert({+inf , 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], u));
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){
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){
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
{
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 f = 0; f < N; ++f){
for(auto &u : scanA[f]){
upd(1 , 0 , M - 1 , revpos[u], L[u].x);
}
for(auto &u : scanD[f]){
upd(1 , 0 , M - 1 , revpos[u], inf);
}
while(lst < q && que[qperm[lst]].se == f){
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[f] - tv);
lst++;
}
}
}
{
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 f = 0; f < N; ++f){
for(auto &u : scanA[f]){
upd(1 , 0 , M - 1 , revpos[u], -R[u].x);
}
for(auto &u : scanD[f]){
upd(1 , 0 , M - 1 , revpos[u], inf);
}
while(lst < q && que[qperm[lst]].se == f){
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[f]);
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
440 ms |
23396 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
405 ms |
22828 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
