#include <bits/stdc++.h>
//#include <quadmath.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define sz(x) (int)x.size()
//#define sqr(x) x*x
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
using namespace std;
//using namespace __gnu_pbds;
//#define int long long
//#define ld long double
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//typedef long long ll;
const int INF = 2e9;
const int MAX_ANS = 1e8;
int nn;
vector<int> t;
void build(int v, int tl, int tr, vector<int>& a)
{
if (tl == tr)
{
t[v] = a[tl];
}
else
{
int tm = (tl + tr) >> 1;
build(v * 2, tl, tm, a);
build(v * 2 + 1, tm + 1, tr, a);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
void update(int v, int tl, int tr, int p, int x)
{
if (tl == tr)
{
t[v] = x;
}
else
{
int tm = (tl + tr) >> 1;
if (p <= tm)
update(v * 2, tl, tm, p, x);
else
update(v * 2 + 1, tm + 1, tr, p, x);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
int get(int v, int tl, int tr, int l, int r)
{
if (l > r || l < tl || tr < r)
return -INF;
if (tl == l && tr == r)
{
return t[v];
}
int tm = (tl + tr) >> 1;
int ql = get(v * 2, tl, tm, l, min(r, tm));
int qr = get(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
return max(ql, qr);
}
//0 - add
//1 - query
//2 - rem
struct ev
{
int x, type, ind, pos;
ev() {}
ev(int x, int type, int ind, int pos) : x(x), type(type), ind(ind), pos(pos) {}
bool operator<(const ev& o)
{
if (x != o.x)
return x < o.x;
if (type != o.type)
return type < o.type;
return ind < o.ind;
}
};
struct store
{
int x, type, a, b;
store() {}
store(int x, int type, int a, int b) : x(x), type(type), a(a), b(b) {}
};
vector<set<pair<int, int> > > type_list;
vector<int> R;
vector<store> sts;
vector<int> compx;
vector<int> rev_compx;
vector<pair<int, int> > comp1;
vector<ev> evs;
vector<int> ans;
vector<pair<int, int> > qs;
vector<int> cnt;
int k;
int query(int b)
{
int ind = lower_bound(comp1.begin(), comp1.end(), make_pair(b, -1)) - comp1.begin() - 1;
int cur = get(1, 0, nn - 1, 0, ind + k);
if (cur == INF)
return INF;
return rev_compx[cur];
}
void solve()
{
int n, q;
cin >> n >> k >> q;
cnt.resize(k);
type_list.resize(k);
sts.resize(n);
comp1.resize(n);
compx.resize(n);
rev_compx.resize(n + k);
qs.resize(q);
ans.resize(q);
R.resize(n + k);
nn = n + k;
for (int i = 0; i < n; i++)
{
int x, t, a, b;
cin >> x >> t >> a >> b;
t--;
compx[i] = x;
sts[i] = {x, t, a, b};
evs.push_back({a, 0, i, x});
evs.push_back({b, 2, i, x});
comp1[i] = {x, i};
}
for (int i = 0; i < q; i++)
{
int t, x;
cin >> x >> t;
qs[i] = {x, t};
evs.push_back({t, 1, i, x});
}
sort(evs.begin(), evs.end());
sort(comp1.begin(), comp1.end());
for (int i = 0; i < n; i++)
{
compx[comp1[i].second] = i + k;
rev_compx[i + k] = comp1[i].first;
}
for (int i = 0; i < k; i++)
{
type_list[i].insert({i, i});
}
for (int i = 0; i < n + k; i++)
{
R[i] = INF;
}
t.resize(4 * nn);
build(1, 0, nn - 1, R);
int cnt_zero = k;
for (auto&[x, type, ind, pos] : evs)
{
if (type == 1)
{
if (cnt_zero)
{
ans[ind] = -1;
}
else
{
int lt = 0, rt = MAX_ANS;
while (rt - lt > 1)
{
int mid = (lt + rt) >> 1;
int beg = pos - mid;
int ed = pos + mid;
int mx = query(beg);
if (mx < ed)
{
rt = mid;
}
else
{
lt = mid;
}
}
ans[ind] = lt;
}
}
else
{
if (type == 0)
{
if (cnt[sts[ind].type] == 0) cnt_zero--;
cnt[sts[ind].type]++;
int t = sts[ind].type;
auto it = type_list[t].lower_bound({compx[ind], -1});
int rt = INF, lt = -INF;
if (it != type_list[t].end()) rt = (*it).first;
if (it != type_list[t].begin()) lt = (*(--it)).first;
R[compx[ind]] = rt;
update(1, 0, nn - 1, compx[ind], rt);
type_list[t].insert({compx[ind], ind});
if (lt != -INF)
{
R[lt] = compx[ind];
update(1, 0, nn - 1, lt, compx[ind]);
}
}
else
{
if (cnt[sts[ind].type] == 1) cnt_zero++;
cnt[sts[ind].type]--;
int t = sts[ind].type;
auto it = type_list[t].upper_bound({compx[ind], ind});
int rt = INF, lt = -INF;
if (it != type_list[t].end()) rt = (*it).first;
it = type_list[t].lower_bound({compx[ind], ind});
if (it != type_list[t].begin()) lt = (*(--it)).first;
if (lt != -INF)
{
R[lt] = rt;
update(1, 0, n - 1, lt, rt);
}
R[compx[ind]] = INF;
update(1, 0, n - 1, compx[ind], INF);
type_list[t].erase({compx[ind], ind});
}
}
}
for (int i = 0; i < q; i++)
{
cout << ans[i] << endl;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
t = 1;
while (t--)
{
solve();
}
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
*/
/*
4 4
1 2 1 3
1 1
1 2
1 3
1 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2597 ms |
57184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2486 ms |
50528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
