#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
cerr << to_string(h);
if(sizeof ...(t)) cerr << ", ";
DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif
const int INF = 1e9 + 7, N = 1e6 + 7;
/*
Multiset using splay tree
Verification: https://loj.ac/s/1129334
*/
struct Splay_tree {
struct node {
int val, cnt, sz;
node *c[2], *p;
node(int _val, node* _p = nullptr) {
val = _val, sz = cnt = 1;
c[0] = c[1] = nullptr, p = _p;
}
};
node* root;
Splay_tree() {
root = nullptr;
}
int sz(node* v) { return v ? v -> sz : 0; }
int dir(node* v) {
if(v -> p) return v -> p -> c[0] == v ? 0 : 1;
return 0;
}
void pull(node* v) {
v -> sz = v -> cnt + sz(v -> c[0]) + sz(v -> c[1]);
}
void link(node* p, node* v, int dir) {
if(p) p -> c[dir] = v;
if(v) v -> p = p;
}
void rot(node* v) { // rotate v up
node* p = v -> p, *g = p -> p;
int d = dir(v), dd = dir(p);
node* b = v -> c[d ^ 1];
link(g, v, dd), link(v, p, d ^ 1), link(p, b, d);
pull(p), pull(v); // order matters!!
}
void splay(node *v) {
while(v -> p) {
if(!(v -> p -> p)) rot(v); // zig
else if(dir(v) != dir(v -> p)) rot(v), rot(v); // zig-zag
else rot(v -> p), rot(v); // zig-zig
}
root = v;
}
node* pre() {
node* v = root -> c[0];
if(!v) return v;
while(v -> c[1]) v = v -> c[1];
return v;
}
node* nxt() {
node* v = root -> c[1];
if(!v) return v;
while(v -> c[0]) v = v -> c[0];
return v;
}
void insert(int val) {
if(!root) {
root = new node(val);
return;
}
node* ptr = root, *lst;
while(ptr) {
lst = ptr;
if(ptr -> val == val) break;
else if(val < ptr -> val) ptr = ptr -> c[0];
else ptr = ptr -> c[1];
}
if(ptr) ptr -> cnt++;
else lst -> c[val > lst -> val] = ptr = new node(val, lst);
splay(ptr);
}
void erase(int val) {
node* v = find(val); // v is now the root
if(!v) return;
v -> cnt--;
if(v -> cnt) pull(v);
else {
if(!v -> c[0] && !v -> c[1]) return root = nullptr, void(0);
if(!v -> c[0]) return root = v -> c[1], root -> p = nullptr, void(0);
node* x = pre();
splay(x);
link(x, v -> c[1], 1);
}
}
node* find(int val) {
if(!root) return nullptr;
node* ptr = root, *lst;
while(ptr && ptr -> val != val) {
lst = ptr;
if(val < ptr -> val) ptr = ptr -> c[0];
else ptr = ptr -> c[1];
}
if(ptr) splay(ptr);
else splay(lst);
return ptr;
}
int order_of_key(int val) {
if(!root) return 0;
node* ptr = root, *lst;
int ans = 0;
while(ptr) {
lst = ptr;
if(val <= ptr -> val) ptr = ptr -> c[0];
else ans += sz(ptr -> c[0]) + ptr -> cnt, ptr = ptr -> c[1];
}
if(ptr) splay(ptr);
else splay(lst);
return ans;
}
int find_by_order(int val) {
assert(val < size());
node* ptr = root;
while(true) {
if(sz(ptr -> c[0]) > val) ptr = ptr -> c[0];
else if(sz(ptr -> c[0]) + ptr -> cnt <= val) val -= (sz(ptr -> c[0]) + ptr -> cnt), ptr = ptr -> c[1];
else {
splay(ptr);
return ptr -> val;
}
}
}
int size() { return sz(root); }
int count(int val) {
node* v = find(val);
return v ? v -> cnt : 0;
}
};
V<pi> G[N];
int ans[N], n, k, q;
vi compress_x, compress_t;
struct DS {
static const int N = 3e5 + 7;
Splay_tree bit[N];
void insert(int pos, int val) {
pos++;
for(; pos < N; pos += pos & -pos)
bit[pos].insert(val);
}
int qry(int pos, int less_than) {
pos++;
int cnt = 0;
for(; pos; pos -= pos & -pos)
cnt += bit[pos].order_of_key(less_than);
return cnt;
}
int qry(int pos){
auto ok = [&] (int d) {
// [pos - d, pos + d]
int lb = lower_bound(ALL(compress_x), pos - d) - compress_x.begin();
int rb = upper_bound(ALL(compress_x), pos + d) - compress_x.begin() - 1;
return qry(rb, lb) - qry(lb - 1, lb) == k;
};
int lb = 0, rb = 1e8;
while(lb <= rb) {
int mb = (lb + rb) / 2;
if(ok(mb)) rb = mb - 1;
else lb = mb + 1;
}
if(lb > 1e8) lb = -1;
return lb;
}
} ds;
struct tseg {
struct node {
};
void upd(int l, int r, int x, int pre) {
}
} tseg;
signed main()
{
IO_OP;
cin >> n >> k >> q;
V<array<int, 4>> stores;
for(int i = 0; i < n; i++) {
int x, type, tl, tr;
cin >> x >> type >> tl >> tr;
stores.PB({x, type, tl, tr});
compress_x.PB(x), compress_t.PB(tl), compress_t.PB(tr);
}
V<pi> qq;
for(int i = 0; i < q; i++) {
int x, t;
cin >> x >> t;
compress_t.PB(t);
qq.EB(x, t);
}
sort(ALL(compress_x));
compress_x.resize(unique(ALL(compress_x)) - compress_x.begin());
sort(ALL(compress_t));
compress_t.resize(unique(ALL(compress_t)) - compress_t.begin());
auto get_x = [&] (int x) {
return int(lower_bound(ALL(compress_x), x) - compress_x.begin());
};
auto get_t = [&] (int t) {
return int(lower_bound(ALL(compress_t), t) - compress_t.begin());
};
sort(ALL(stores));
map<int, int> mp;
for(auto p:stores) {
int x = get_x(p[0]), type = p[1], tl = get_t(p[2]), tr = get_t(p[3]);
int pre = (mp.count(type) ? mp[type] : -1);
//tseg.upd(tl, tr + 1, x, pre);
ds.insert(x, pre);
mp[type] = x;
}
for(int i = 0; i < int(qq.size()); i++) {
pi p = qq[i];
int x = p.F, t = get_t(p.S);
// G[t].EB(i, x);
ans[i] = ds.qry(x);
}
for(int i = 0; i < q; i++)
cout << ans[i] << '\n';
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:243:37: warning: unused variable 'tl' [-Wunused-variable]
243 | int x = get_x(p[0]), type = p[1], tl = get_t(p[2]), tr = get_t(p[3]);
| ^~
new_home.cpp:243:55: warning: unused variable 'tr' [-Wunused-variable]
243 | int x = get_x(p[0]), type = p[1], tl = get_t(p[2]), tr = get_t(p[3]);
| ^~
new_home.cpp:252:16: warning: unused variable 't' [-Wunused-variable]
252 | int x = p.F, t = get_t(p.S);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
26060 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
26064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
26060 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
26064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5050 ms |
154160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5072 ms |
174248 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
26060 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
26064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
26060 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
26064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
