#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5;
const int MAXV = 1e8;
int n, k, q;
class event {
public:
int time;
bool type; // 0 update, 1 query
bool start_or_end; // 0 start, 1 end. Only for updates
int store_type; // update only
int pos; // both
int id; // query
event(int tim, bool se, int tp, int p) {
time = tim;
type = 0;
start_or_end = se;
store_type = tp;
pos = p;
}
event(int tim, int p, int i) {
type = 1;
time = tim;
pos = p;
id = i;
}
};
bool operator<(event &a, event &b) {
return (a.time == b.time) ? (a.type < b.type) : (a.time < b.time);
}
vector<event> events;
int answs[MAXN];
int cnt[MAXN];
int num_active = 0;
multiset<int> locs[MAXN];
class stree {
public:
int lp, rp;
stree *l = nullptr;
stree *r = nullptr;
int mx;
multiset<int> all_vals; // only for lowest level
stree(int lv, int rv) {
mx = 0;
lp = lv;
rp = rv;
}
int mxq(int lv, int rv) {
if (lp > rv || rp < lv) return 0;
if (lp >= lv && rp <= rv) return mx;
int best = 0;
if (l) best = max(best, l->mxq(lv, rv));
if (r) best = max(best, r->mxq(lv, rv));
return best;
}
void update(int p, int v) {
if (lp == rp) {
all_vals.insert(v);
mx = *(all_vals.rbegin());
return;
}
int m = (lp+rp)/2;
if (p <= m) {
if (!l) l = new stree(lp, m);
l->update(p, v);
}
else {
if (!r) r = new stree(m+1, rp);
r->update(p, v);
}
mx = 0;
if (l) mx = max(mx, l->mx);
if (r) mx = max(mx, r->mx);
}
void deupdate(int p, int v) {
if (lp == rp) {
all_vals.erase(all_vals.find(v));
if (all_vals.empty()) mx = 0;
else mx = *(all_vals.rbegin());
return;
}
int m = (lp+rp)/2;
if (p <= m) {
if (!l) l = new stree(lp, m);
l->deupdate(p, v);
}
else {
if (!r) r = new stree(m+1, rp);
r->deupdate(p, v);
}
mx = 0;
if (l) mx = max(mx, l->mx);
if (r) mx = max(mx, r->mx);
}
};
stree *ltree, *rtree;
void make(int l, int r) {
return;
if (l == -1 && r == -1) return;
if (l == -1) {
ltree->update(0, r);
return;
}
if (r == -1) {
rtree->update(MAXV, MAXV-l);
return;
}
int p1 = (l+r)/2;
int p2 = (l+r+1)/2;
int v1 = MAXV-l;
int v2 = r;
ltree->update(p2, v2);
rtree->update(p1, v1);
}
void unmake(int l, int r) {
return;
if (l == -1 && r == -1) return;
if (l == -1) {
ltree->deupdate(0, r);
return;
}
if (r == -1) {
rtree->deupdate(MAXV, MAXV-l);
return;
}
int p1 = (l+r)/2;
int p2 = (l+r+1)/2;
int v1 = MAXV-l;
int v2 = r;
ltree->deupdate(p2, v2);
rtree->deupdate(p1, v1);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> k >> q;
ltree = new stree(0, MAXV);
rtree = new stree(0, MAXV);
for (int i = 0; i < n; i++) {
int x, t, a, b;
cin >> x >> t >> a >> b; t--;
events.push_back(event(a, 0, t, x));
events.push_back(event(b+1, 1, t, x));
}
for (int i = 0; i < q; i++) {
int x, t; cin >> x >> t;
events.push_back(event(t, x, i));
}
sort(events.begin(), events.end());
for (event ev: events) {
if (ev.type == 0) {
int type = ev.store_type;
if (ev.start_or_end == 0) {
num_active += (cnt[type] == 0);
cnt[type]++;
if (locs[type].find(ev.pos) != locs[type].end()) {
locs[type].insert(ev.pos);
continue;
}
auto iter = locs[type].lower_bound(ev.pos);
int r = -1;
int l = -1;
if (iter != locs[type].end()) r = *iter;
if (iter != locs[type].begin()) {
iter--;
l = *iter;
}
unmake(l, r);
locs[type].insert(ev.pos);
make(l, ev.pos);
make(ev.pos, r);
}
else {
cnt[type]--;
num_active -= (cnt[type] == 0);
locs[type].erase(locs[type].find(ev.pos));
if (locs[type].find(ev.pos) != locs[type].end()) continue;
auto iter = locs[type].lower_bound(ev.pos);
int r = -1;
int l = -1;
if (iter != locs[type].end()) r = *iter;
if (iter != locs[type].begin()) {
iter--;
l = *iter;
}
make(l, r);
unmake(l, ev.pos);
unmake(ev.pos, r);
}
}
if (ev.type == 1) {
if (num_active < k) {
answs[ev.id] = -1;
continue;
}
answs[ev.id] = max(ltree->mxq(0, ev.pos)-ev.pos, rtree->mxq(ev.pos, MAXV)-MAXV+ev.pos);
}
}
for (int i = 0; i < q; i++) cout << answs[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
368 ms |
50360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
546 ms |
49936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
