#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
template<typename T>
struct segtree {
// https://codeforces.com/blog/entry/18051
/*=======================================================*/
struct data {
ll a;
};
data neutral = {0};
data merge(data &left, data &right) {
data curr;
curr.a = max(left.a,right.a);
return curr;
}
void create(int i, T v) {
}
void modify(int i, T v) {
tr[i].a = v;
}
/*=======================================================*/
int n;
vector<data> tr;
segtree() {
}
segtree(int siz) {
init(siz);
}
void init(int siz) {
n = siz;
tr.assign(2 * n, neutral);
}
void build(vector<T> &a, int siz) {
rep(i, siz) create(i + n, a[i]);
rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
}
void pupd(int i, T v) {
modify(i + n, v);
for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
}
data query(int l, int r) {
data resl = neutral, resr = neutral;
for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
if (l & 1) resl = merge(resl, tr[l++]);
if (!(r & 1)) resr = merge(tr[r--], resr);
}
return merge(resl, resr);
}
};
void solve(int test_case)
{
ll n,k,q; cin >> n >> k >> q;
vector<array<ll,4>> a(n+5);
rep1(i,n) rep(j,4) cin >> a[i][j];
vector<ll> b;
map<ll,vector<array<ll,3>>> mp;
rep1(i,n){
auto [x,t,l,r] = a[i];
mp[l].pb({1,t,x});
mp[r+1].pb({2,t,x});
b.pb(x);
}
rep1(id,q){
ll x,y; cin >> x >> y;
mp[y].pb({3,id,x});
b.pb(x);
}
b.pb(-inf2), b.pb(inf2);
sort(all(b));
b.resize(unique(all(b))-b.begin());
ll siz = sz(b);
multiset<ll> ms[k+5];
multiset<ll> pos[siz];
segtree<ll> st(siz);
rep1(i,k){
pos[i].insert(0), pos[i].insert(siz-1);
ms[0].insert(siz-1);
}
st.pupd(0,siz-1);
auto upd = [&](ll op, ll l, ll r){
if(op == 1){
ms[l].insert(r);
st.pupd(l,*ms[l].rbegin());
}
else{
ms[l].erase(ms[l].find(r));
if(ms[l].empty()){
st.pupd(l,0);
}
else{
st.pupd(l,*ms[l].rbegin());
}
}
};
auto add = [&](ll t, ll x){
x = lower_bound(all(b),x)-b.begin();
pos[t].insert(x);
auto it = pos[t].find(x);
ll l = -1, r = -1;
if(it != pos[t].begin()){
l = *prev(it);
}
if(next(it) != pos[t].end()){
r = *next(it);
}
assert(l != -1 and r != -1);
upd(2,l,r);
upd(1,l,x);
upd(1,x,r);
};
auto rem = [&](ll t, ll x){
x = lower_bound(all(b),x)-b.begin();
auto it = pos[t].find(x);
ll l = -1, r = -1;
if(it != pos[t].begin()){
l = *prev(it);
}
if(next(it) != pos[t].end()){
r = *next(it);
}
assert(l != -1 and r != -1);
pos[t].erase(it);
upd(2,l,x);
upd(2,x,r);
upd(1,l,r);
};
vector<ll> ans(q+5,-1);
for(auto [ti,v] : mp){
for(auto [t,typ,x] : v){
if(t == 1){
add(typ,x);
}
else if(t == 2){
// rem(typ,x);
}
else{
ll id = typ;
ll lo = 0, hi = 1e8;
while(lo <= hi){
ll mid = (lo+hi) >> 1;
ll ind = lower_bound(all(b),x-mid)-b.begin();
ll mxr = st.query(0,ind-1).a;
if(b[mxr]-x <= mid){
ans[id] = mid;
hi = mid-1;
}
else{
lo = mid+1;
}
}
}
}
}
rep1(i,q) cout << ans[i] << endl;
}
int main()
{
fastio;
int t = 1;
// cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Compilation message
new_home.cpp: In function 'void solve(int)':
new_home.cpp:199:10: warning: variable 'rem' set but not used [-Wunused-but-set-variable]
199 | auto rem = [&](ll t, ll x){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
532 ms |
245608 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
873 ms |
279176 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
