#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
/*
sweep through time, answer queries offline
for a given query, do b.s
when mid is fixed, we get a range [l,r]
find if all types [1..k] are present in [l,r]
key idea:
at a given time, lets say for a given type of shop t, the active positions are p[1],p[2],...,p[m]
then if [l,r] lies in any of the segs [1,p[1]-1],[p[1]+1,p[2]-1],[p[2]+1,p[3]-1],...,[p[m]+1,MAX(=1e8)], then [l,r] is bad
otherwise, [l,r] is good
checking this efficiently can be done with a range max segtree
all ranges can be maintained efficiently with a multiset
*/
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 {
int 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)
{
int n,k,q; cin >> n >> k >> q;
vector<array<int,4>> a(n+5);
rep1(i,n) rep(j,4) cin >> a[i][j];
vector<int> b;
map<int,vector<array<int,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){
int x,y; cin >> x >> y;
mp[y].pb({3,id,x});
b.pb(x);
}
b.pb(-inf1), b.pb(inf1);
sort(all(b));
b.resize(unique(all(b))-b.begin());
int siz = sz(b);
multiset<int> pos[k+5];
multiset<int> ms[siz];
segtree<int> 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 = [&](int op, int l, int 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 = [&](int t, int x){
x = lower_bound(all(b),x)-b.begin();
pos[t].insert(x);
auto it = pos[t].find(x);
int 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 = [&](int t, int x){
x = lower_bound(all(b),x)-b.begin();
auto it = pos[t].find(x);
int 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<int> 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{
int id = typ;
int lo = 0, hi = 1e8;
while(lo <= hi){
int mid = (lo+hi) >> 1;
int ind = lower_bound(all(b),x-mid)-b.begin();
int 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
128 ms |
73972 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1372 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
122 ms |
74260 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1112 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
115 ms |
69136 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
