#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 6e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
struct event {
int y,id,t;
event(int _y = 0, int _id = 0, int _t = 0) {
y = _y;
id = _id;
t = _t;
}
bool operator < (const event &e) const {
return y < e.y || (y == e.y && t < e.t);
}
};
struct segtree {
bool mx;
int n;
vector <int> st;
segtree(int _n = 0, bool _mx = 0) {
mx = _mx;
n = _n;
st.assign((n << 2) + 5, mx ? -oo : oo);
}
void update(int id, int l, int r, int pos, int val) {
if (l > pos || r < pos)
return;
if (l == r) {
st[id] = val;
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, pos, val);
update(id << 1 | 1, mid + 1, r, pos, val);
if (mx)
st[id] = max(st[id << 1], st[id << 1 | 1]);
else
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
void update(int pos, int val) {
update(1, 1, n, pos, val);
}
int getminl(int id, int l, int r, int x) {
if (st[id] < x)
return oo;
if (l == r)
return l;
int mid = (l + r) >> 1;
int res = getminl(id << 1, l, mid, x);
if (res == oo)
res = getminl(id << 1 | 1, mid + 1, r, x);
return res;
}
int getminl(int x) {
return getminl(1, 1, n, x);
}
int getmaxr(int id, int l, int r, int x) {
if (st[id] > x)
return -oo;
if (l == r)
return l;
int mid = (l + r) >> 1;
int res = getmaxr(id << 1 | 1, mid + 1, r, x);
if (res == -oo)
res = getmaxr(id << 1, l, mid, x);
return res;
}
int getmaxr(int x) {
return getmaxr(1, 1, n, x);
}
};
segtree minl, maxr;
multiset <int> candl[N];
multiset <int> candr[N];
multiset <int> pos[N];
vector <event> events;
vector <int> pos_x;
int ans[N];
int _x[N];
int t[N];
int n,k,q,sz,cnt;
int getind(int x) {
return upper_bound(ALL(pos_x), x) - pos_x.begin();
}
int getans(int x) {
int pos = getind(x);
int l = minl.getminl(pos);
int r = maxr.getmaxr(pos);
int res = -1;
if (l <= pos)
maxi(res, pos_x[pos - 1] - pos_x[l - 1]);
if (pos <= r)
maxi(res, pos_x[r - 1] - pos_x[pos - 1]);
return res;
}
void updatemax(int pos) {
maxr.update(pos, *candr[pos].begin());
}
void updatemin(int pos) {
minl.update(pos, *prev(candl[pos].end()));
}
void add(int l, int r, int t) {
int mid = (l + r) >> 1;
int pl = getind(l);
int pr = getind(r);
int pmid = getind(mid);
if (t > 0) {
candl[pmid].insert(pl);
updatemin(pmid);
if (pmid < pr) {
candr[pr].insert(pmid + 1);
updatemax(pr);
}
} else {
candl[pmid].erase(candl[pmid].find(pl));
updatemin(pmid);
if (pmid < pr) {
candr[pr].erase(candr[pr].find(pmid + 1));
updatemax(pr);
}
}
}
void solve(vector <pair <int, int>> events) {
for (pair <int, int> pir : events) {
// cerr << cnt << "\n";
int x = _x[pir.fi];
int c = t[pir.fi];
int p = getind(x);
// cerr << pir.fi << " " << pir.se << " " << x << " " << c << "\n";
if (pir.se == 2) {
ans[pir.fi - n] = (cnt < k) ? -1 : getans(x);
// cerr << "ans = " << ans[pir.fi - n] << "\n";
} else if (pir.se == 0) {
if (!pos[c].size()) {
cnt++;
candr[p].insert(1);
candl[p].insert(sz);
updatemax(p);
updatemin(p);
pos[c].insert(x);
continue;
}
auto it = pos[c].lower_bound(x);
if (it == pos[c].begin()) {
int tmp = getind(*it);
candr[tmp].erase(candr[tmp].find(1));
candr[p].insert(1);
updatemax(tmp);
updatemax(p);
add(x, *it, 1);
pos[c].insert(x);
continue;
}
if (it == pos[c].end()) {
it--;
int tmp = getind(*it);
candl[tmp].erase(candl[tmp].find(sz));
candl[p].insert(sz);
updatemin(tmp);
updatemin(p);
add(*it, x, 1);
pos[c].insert(x);
continue;
}
int l = *prev(it);
int r = *it;
add(l, r, -1);
add(l, x, 1);
add(x, r, 1);
pos[c].insert(x);
} else {
pos[c].erase(pos[c].find(x));
if (!pos[c].size()) {
candr[p].erase(candr[p].find(1));
candl[p].erase(candl[p].find(sz));
updatemax(p);
updatemin(p);
cnt--;
continue;
}
auto it = pos[c].lower_bound(x);
if (it == pos[c].begin()) {
int tmp = getind(*it);
candr[tmp].insert(1);
candr[p].erase(candr[p].find(1));
updatemax(p);
updatemax(tmp);
add(x, *it, -1);
continue;
}
if (it == pos[c].end()) {
it--;
int tmp = getind(*it);
candl[tmp].insert(sz);
candl[p].erase(candl[p].find(sz));
updatemin(p);
updatemin(tmp);
add(*it, x, -1);
continue;
}
int l = *prev(it);
int r = *it;
add(l, r, 1);
add(l, x, -1);
add(x, r, -1);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef ONLINE_JUDGE
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
#endif
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) {
int a,b;
cin >> _x[i] >> t[i] >> a >> b;
events.push_back(event(a, i, 0));
events.push_back(event(b + 1, i, 1));
pos_x.push_back(_x[i]);
}
for (int i = 1; i <= q; i++) {
int y;
cin >> _x[n + i] >> y;
events.push_back(event(y, n + i, 2));
pos_x.push_back(_x[n + i]);
}
sort(ALL(pos_x));
sz = n + q;
minl = segtree(sz, 1);
maxr = segtree(sz, 0);
for (int i = 1; i <= sz; i++) {
candl[i].insert(-oo);
candr[i].insert(oo);
}
sort(ALL(events));
for (int l = 0; l < (int) events.size();) {
int r = l;
while (r < (int) events.size() && events[l].y == events[r].y)
r++;
vector <pair <int, int>> pir;
for (int i = l; i < r; i++)
pir.push_back(mp(events[i].id, events[i].t));
solve(pir);
l = r;
}
for (int i = 1; i <= q; i++)
cout << ans[i] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
84820 KB |
Output is correct |
| 2 |
Correct |
45 ms |
84756 KB |
Output is correct |
| 3 |
Correct |
40 ms |
84812 KB |
Output is correct |
| 4 |
Incorrect |
44 ms |
84816 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
84820 KB |
Output is correct |
| 2 |
Correct |
45 ms |
84756 KB |
Output is correct |
| 3 |
Correct |
40 ms |
84812 KB |
Output is correct |
| 4 |
Incorrect |
44 ms |
84816 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3302 ms |
230848 KB |
Output is correct |
| 2 |
Incorrect |
4097 ms |
240960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4198 ms |
227972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
84820 KB |
Output is correct |
| 2 |
Correct |
45 ms |
84756 KB |
Output is correct |
| 3 |
Correct |
40 ms |
84812 KB |
Output is correct |
| 4 |
Incorrect |
44 ms |
84816 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
84820 KB |
Output is correct |
| 2 |
Correct |
45 ms |
84756 KB |
Output is correct |
| 3 |
Correct |
40 ms |
84812 KB |
Output is correct |
| 4 |
Incorrect |
44 ms |
84816 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
