#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define INF 1e9
using namespace std;
#define pii pair<int, int>
namespace seg {
const int P = 5e7;
int p = 0, root = 0;
vector<int> lch, rch, seg;
int get_new() {return ++p;}
void init_() {
lch.assign(P, 0);
rch.assign(P, 0);
seg.assign(P, INF);
root = get_new();
}
void pull(int nd) {
seg[nd] = min(seg[lch[nd]], seg[rch[nd]]);
}
void modify(int nd, int L, int R, int x, int v) {
if(L == R) seg[nd] = v;
else {
int mid = (L + R) / 2;
if(!lch[nd]) lch[nd] = get_new();
if(!rch[nd]) rch[nd] = get_new();
if(x <= mid) modify(lch[nd], L, mid, x, v);
else modify(rch[nd], mid + 1, R, x, v);
pull(nd);
}
}
/* int query(int nd, int L, int R, int l, int r) {
if(!nd) return INF;
else if(l <= L && r >= R) return seg[nd];
else {
int mid = (L + R) / 2;
return min(query(lch[nd], L, mid, l, r),
query(rch[nd], mid + 1, R, l, r));
}
}
*/
int get_lb(int nd, int L, int R, int x, int cur) {
int mid = (L + R) / 2;
if(!nd) return abs(x - max(L, x));
else if(L == R) {
int l = 2 * x - L;
if(L == INF || cur < l) return -1;
else return L - x;
}
else {
int mid = (L + R) / 2, l = 2 * x - mid;
if(min(cur, seg[rch[nd]]) >= l)
return get_lb(lch[nd], L, mid, x, min(cur, seg[rch[nd]]));
else return get_lb(rch[nd], mid + 1, R, x, cur);
}
}
/* int ask(int x) {
return query(root, 1, INF, x, INF);
}
*/ int answer(int x) {
return get_lb(root, 1, INF, x, INF);
}
void change(int x, int v) {
modify(root, 1, INF, x, v);
}
};
namespace solver {
int n, k, q;
struct query {
int x, tp, id;
bool operator<(query b) {
if(x != b.x) return x < b.x;
else return tp < b.tp;
}
};
vector<map<int, int>> s;
vector<multiset<pii>> cur;
vector<pii> ans, stores;
vector<query> qq;
vector<int> v;
void init_(int _n, int _k, int _q) {
n = _n, k = _k, q = _q;
s.assign(k + 1, map<int, int>());
cur.assign(n + q + 2, multiset<pii>());
ans.assign(q + 1, {0, 0});
stores.assign(n + k + 1, {0, 0});
qq.clear(), v.clear();
seg::init_();
}
void add_store(int id, int l, int tp, int a, int b) {
stores[id] = {l, tp};
v.push_back(l);
qq.push_back({a, 1, id});
qq.push_back({b + 1, 2, id});
}
void add_query(int id, int l, int y) {
ans[id].first = l;
v.push_back(l);
qq.push_back({y, 3, id});
}
void update(int x) {
auto it = cur[x].begin();
if(it == cur[x].end()) seg::change(v[x], INF);
else seg::change(v[x], v[it -> first]);
}
void add(int id) {
int tp = stores[id].second, l = stores[id].first;
s[tp][l] ++;
if(s[tp][l] > 1) return;
int pre, nxt = 0;
auto it1 = s[tp].upper_bound(l);
auto it2 = s[tp].lower_bound(l);
if(it2 == s[tp].begin()) pre = 0;
else pre = prev(it2) -> first;
if(it1 != s[tp].end()) {
nxt = it1 -> first;
cur[nxt].erase(cur[nxt].find({pre, tp}));
cur[nxt].insert({l, tp});
update(nxt);
}
cur[l].insert({pre, tp});
update(l);
}
int query(int x) {
return seg::answer(x);
}
/* int query(int x) {
int L = -1, R = 1e8;
while(R - L > 1) {
int mid = (L + R) / 2;
int val = seg::ask(x + mid + 1);
if(val < x - mid) L = mid;
else R = mid;
}
if(R == 1e8) return -1;
else return R;
}
*/ void remove(int id) {
int tp = stores[id].second, l = stores[id].first;
s[tp][l] --;
if(s[tp][l] > 0) return;
int pre, nxt;
s[tp].erase(s[tp].find(l));
auto it1 = s[tp].upper_bound(l);
auto it2 = s[tp].lower_bound(l);
if(it2 == s[tp].begin()) pre = 0;
else pre = prev(it2) -> first;
if(it1 != s[tp].end()) {
nxt = it1 -> first;
cur[nxt].erase(cur[nxt].find({l, tp}));
cur[nxt].insert({pre, tp});
update(nxt);
}
cur[l].erase({pre, tp});
update(l);
}
void solve() {
rep(i, 1, k) add_store(n + i, INF, i, -INF, INF);
v.push_back(-INF);
sort(all(v)), v.resize(unique(all(v)) - v.begin());
rep(i, 1, n + k) stores[i].first = lower_bound(all(v), stores[i].first) - v.begin();
rep(i, 1, q) ans[i].first = lower_bound(all(v), ans[i].first) - v.begin();
sort(all(qq));
for(auto i : qq) {
if(i.tp == 1) add(i.id);
else if(i.tp == 2) remove(i.id);
else ans[i.id].second = query(v[ans[i.id].first]);
}
rep(i, 1, q) cout << ans[i].second << "\n";
}
};
using namespace solver;
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int n, k, q; cin >> n >> k >> q;
init_(n, k, q);
rep(i ,1, n) {
int x, t, a, b;
cin >> x >> t >> a >> b;
add_store(i, x, t, a, b);
}
rep(i, 1, q) {
int l, y; cin >> l >> y;
add_query(i, l, y);
}
solve();
return 0;
}
Compilation message
new_home.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
4 | #pragma loop-opt(on)
|
new_home.cpp: In function 'int seg::get_lb(int, int, int, int, int)':
new_home.cpp:48:7: warning: unused variable 'mid' [-Wunused-variable]
48 | int mid = (L + R) / 2;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
296 ms |
587332 KB |
Output is correct |
| 2 |
Correct |
298 ms |
587304 KB |
Output is correct |
| 3 |
Correct |
300 ms |
587404 KB |
Output is correct |
| 4 |
Incorrect |
302 ms |
587324 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
296 ms |
587332 KB |
Output is correct |
| 2 |
Correct |
298 ms |
587304 KB |
Output is correct |
| 3 |
Correct |
300 ms |
587404 KB |
Output is correct |
| 4 |
Incorrect |
302 ms |
587324 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3036 ms |
674596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3217 ms |
664728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
296 ms |
587332 KB |
Output is correct |
| 2 |
Correct |
298 ms |
587304 KB |
Output is correct |
| 3 |
Correct |
300 ms |
587404 KB |
Output is correct |
| 4 |
Incorrect |
302 ms |
587324 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
296 ms |
587332 KB |
Output is correct |
| 2 |
Correct |
298 ms |
587304 KB |
Output is correct |
| 3 |
Correct |
300 ms |
587404 KB |
Output is correct |
| 4 |
Incorrect |
302 ms |
587324 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
