#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = (int)1.5e6 + 10;
const int inf = 1e9;
struct seg{
int a[4*N];
int p[4*N];
void clr(int x = inf){
fill(a , a + 4 * N , x);
fill(p , p + 4 * N , x);
}
void push(int v){
int v1 = v << 1;
for(auto u : {v1 , v1|1}){
a[u] = min(a[u] , p[v]);
p[u] = min(p[u] , p[v]);
}
p[v] = inf;
}
int get(int v , int tl , int tr , int l , int r){
if(tl == l && tr == r){
return a[v];
}
int mid = (tl + tr) >> 1 , v1 = v << 1;
push(v);
int ans = inf;
if(l <= mid)
ans = min(ans , get(v1, tl , mid , l , r));
if(r > mid)
ans = min(ans , get(v1 | 1, mid + 1 , tr , max(l , mid + 1), r));
return ans;
}
void upd(int v , int tl , int tr , int l , int r , int val){
if(tl == l && tr == r){
p[v] = min(p[v] , val);
a[v] = min(a[v] , val);
return;
}
int mid = (tl + tr) >> 1 , v1 = v << 1;
push(v);
if(l <= mid)
upd(v1 , tl , mid , l , min(r , mid) , val);
if(r > mid)
upd(v1 | 1 , mid + 1 , tr , max(l , mid + 1) , r, val);
a[v] = min(a[v1] , a[v1|1]);
}
}MN,MX;
mt19937 rng(199999999973);
vector < pair < int , int > > open[N];
vector < pair < int , int > > close[N];
multiset < int > type[N];
vector < int > pos[N];
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
bool debug = 0;
int n , k , q;
if(!debug){
cin >> n >> k >> q;
}else{
n = (int)3e5;
k = (int)500;
q = (int)3e5;
}
vector < int > x(n), t(n), a(n), b(n);
vector < int > zipyear;
for(int i = 0; i < n; ++i){
if(!debug)
cin >> x[i] >> t[i] >> a[i] >> b[i];
else{
x[i] = rng() % (int)1e8;
t[i] = rng() % k + 1;
a[i] = 1;
b[i] = rng() % int(1e8) + 1;
if(a[i] > b[i])swap(a[i], b[i]);
}
b[i]++;
zipyear.pb(a[i]), zipyear.pb(b[i]);
}
vector < pair < int , int >> que(q);
for(auto &i : que){
if(!debug)
cin >> i.fi >> i.se;
else{
i.fi = rng() % (int)1e8;
i.se = rng() % (int)1e8;
}
zipyear.pb(i.se);
}
sort(all(zipyear)), zipyear.erase(unique(all(zipyear)), zipyear.end());
for(int i = 0; i < n; ++i){
a[i] = lower_bound(all(zipyear), a[i]) - zipyear.begin();
b[i] = lower_bound(all(zipyear), b[i]) - zipyear.begin();
}
for(int i = 0; i < q; ++i){
que[i].se = lower_bound(all(zipyear), que[i].se) - zipyear.begin();
}
vector < int > answer(q, -1);
vector < pair < int , int > > pr;
for(int i = 0; i < q; ++i)
pr.pb({que[i].se, i});
sort(all(pr));
int year = -1;
bool ONE = 1;
for(int i = 0; i < n; ++i){
if(a[i] != 0)
ONE = 0;
}
if(k <= 400 && !ONE){
for(int i = 0; i < n; ++i){
open[a[i]].push_back({t[i], x[i]});
close[b[i]].push_back({t[i], x[i]});
}
/// inc
for(auto &i : pr){
while(year + 1 <= i.fi){
/// lol
for(auto &shop : open[year + 1]){
type[shop.fi].insert(shop.se);
}
/// lol
for(auto &shop : close[year + 1]){
type[shop.fi].erase(type[shop.fi].find(shop.se));
}
year++;
}
int ans = -1;
//
// cout << "LOL " << i.fi << ' ' << "\n";
// for(int t =1 ;t <=k; ++t){
// cout << "TYPE " << t << '\n';
// for(auto &u : type[t])
// cout << u << ' ';
// cout << endl;
// }
for(int t = 1;t <= k; ++t){
if(type[t].empty()){
ans = -1;
break;
}
int dist = 1e9;
auto it = type[t].lower_bound(que[i.se].fi);
if(it != type[t].end())
dist = min(dist , *it - que[i.se].fi);
if(it != type[t].begin()){
--it;
dist = min(dist , que[i.se].fi - *it);
}
ans = max(ans , dist);
}
answer[i.se] = ans;
}
}else if(true){
vector < int > cord;
cord = x;
for(auto &i : que)
cord.pb(i.fi);
sort(all(cord));
cord.erase(unique(all(cord)) , cord.end());
for(int i = 0; i < n; ++i){
x[i] = lower_bound(all(cord), x[i]) - cord.begin();
}
for(int i = 0; i < n; ++i){
open[a[i]].push_back({t[i], x[i]});
close[b[i]].push_back({t[i], x[i]});
}
// if(sz())
MN.clr(), MX.clr();
assert(sz(cord) <= N);
// return 0;
for(int i = 0; i < sz(cord); ++i){
MN.upd(1 , 0 , N-1, i , i , cord[i]);
MX.upd(1 , 0 , N-1, i , i , -cord[i]);
}
for(int i = 0 ; i< n; ++i){
pos[t[i]].pb(x[i]);
}
auto put = [&](int L , int R){
// return;
if(L == R){
MN.upd(1 , 0, N-1 , L, L, cord[L]);
MX.upd(1 , 0, N-1 , L, L, -cord[L]);
return;
}
int l = L;
int r = R;
if(L > R)
assert(false);
while(l != r){
// cout << l << ' ' << r << endl;
int m = (l + r) >> 1;
if(cord[m] - cord[L] <= cord[R] - cord[m]){
if(l + 1 == r)
l = r;
else
l = m;
}else
r = m;
}
// if(r - 1 < L)assert(false);
// if(r > R)assert(false);
assert(r - 1 >= L);
assert(r <= R);
MN.upd(1 , 0 , N - 1 , L , r - 1, cord[L]);
MX.upd(1 , 0 , N - 1 , r , R , -cord[R]);
};
assert(N >= sz(cord));
// return 0;
auto putbegin = [&](int X){
assert(X>0&&X<sz(cord));
MX.upd(1 , 0 , N-1, 0 , X, -cord[X]);
};
auto putend = [&](int X){
MN.upd(1 , 0 , N - 1 , X , sz(cord) - 1, cord[X]);
};
auto gt = [&](int X){
assert(X >= 0 && X < sz(cord));
int val = MN.get(1 , 0 , N - 1 , X , X);
int val1 = MX.get(1 , 0 , N-1 , X , X);
return max((cord[X]-val), -val1 - cord[X]);
};
for(int t = 1; t <= k; ++t){
sort(all(pos[t]));
/// 0
if(pos[t].empty())
continue;
putbegin(pos[t][0]);
putend(pos[t].back());
for(int i = 0; i < sz(pos[t]) - 1; ++i){
put(pos[t][i], pos[t][i+ 1]);
}
}
bool done = 0;
// cout << "HERE\n";
// return 0;
vector < int > diff(k + 1);
for(int i = 0; i < n; ++i)
diff[t[i]] = 1;
for(int t = 1; t <= k; ++t){
if(!diff[t]){
for(int i = 0 ; i < q; ++i)
cout << -1 << '\n';
return 0;
}
}
for(auto &i : pr){
while(year + 1 <= i.fi){
/// lol
for(auto &shop : open[year + 1]){
type[shop.fi].insert(shop.se);
}
/// lol
for(auto &shop : close[year + 1]){
type[shop.fi].erase(type[shop.fi].find(shop.se));
if(type[shop.fi].empty()){
done = 1;
break;
}
auto it = type[shop.fi].lower_bound(shop.se);
if(it != type[shop.fi].begin() && it != type[shop.fi].end()){
auto it1 = it;it1--;
put(*it1 , *it);
} else{
if(it == type[shop.fi].end()){
--it;
putend(*it);
}else{
putbegin(*it);
}
}
}
if(done)
break;
year++;
}
if(done)
break;
// cout << " ITTER " << i.fi << ' ' << year << endl;
//
// cout << "YEAR\n";
// for(int t = 1; t <= k; ++t){
// cout << "SZ " << t << ' ' << type[t].size() << endl;
// }
// cout << "LOL\n";
int ps = lower_bound(all(cord) , que[i.se].fi) - cord.begin();
answer[i.se] = gt(ps);
}
}
for(int i = 0 ; i < q; ++i)
cout << answer[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 1 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1
1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
308 ms |
548036 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
308 ms |
548036 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1342 ms |
596780 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
969 ms |
608872 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
308 ms |
548036 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
308 ms |
548036 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
