//Pantyhose(black) + glasses = infinity
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "new_home"
const int MAX_N = 300002;
const int INF = 1e9+100;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct treap {
struct item {
int L, R, max_r, prior;
item *l, *r;
item(int L=0, int R=0): L(L), R(R) {
max_r = R;
prior = uniform_int_distribution<int>(1, INF)(rng);
// prior = 1;
l = r = nullptr;
}
};
typedef item * pitem;
pitem root = nullptr;
int get_max_r(pitem t) {
return t ? t->max_r : 0;
}
void upd(pitem t) {
if (t)
t->max_r = max(t->R, max(get_max_r(t->l), get_max_r(t->r)));
}
void split(pitem t, pitem &l, pitem &r, int key) {
if (!t) {
l = r = nullptr;
}
else {
if (key>t->L)
split(t->r, t->r, r, key), l = t;
else
split(t->l, l, t->l, key), r = t;
}
upd(t);
}
void merge(pitem &t, pitem l, pitem r) {
if (!l || !r) {
t = l ? l : r;
}
else {
if (l->prior>r->prior)
merge(l->r, l->r, r), t = l;
else
merge(r->l, l, r->l), t = r;
}
upd(t);
}
void insert(pitem &t, pitem it) {
if (!t) {
t = it;
}
else {
if (it->prior>t->prior)
split(t, it->l, it->r, it->L), t = it;
else
insert(it->L<t->L ? t->l : t->r, it);
}
upd(t);
}
void erase(pitem &t, int L, int R) {
if (!t)
return;
if (t->L==L && t->R==R)
merge(t, t->l, t->r);
else
erase(L<t->L ? t->l : t->r, L, R);
upd(t);
}
int get(pitem t, int L) {
if (!t)
return -INF;
if (L<t->L)
return get(t->l, L);
return max(max(t->R, get_max_r(t->l)), get(t->r, L));
}
void insert(int L, int R) {
insert(root, new item(L, R));
}
void erase(int L, int R) {
erase(root, L, R);
}
int get(int L) {
return get(root, L);
}
};
struct store {
int x, t, a, b;
};
struct query {
int l, y;
};
int n, k, nQueries, res[MAX_N];
vector<int> T, store_event[MAX_N*3], q[MAX_N*3];
store s[MAX_N];
query Q[MAX_N];
map<int, int> pos[MAX_N*3];
treap interval_set;
int read_int() {
char c;
for (c = getchar(); c<'0' || c>'9'; c = getchar());
int res = c - '0';
for (c = getchar(); '0'<=c && c<='9'; c = getchar())
res = res * 10 + c - '0';
return res;
}
void read_input() {
n = read_int();
k = read_int();
nQueries = read_int();
for (int i=1; i<=n; ++i) {
s[i].x = read_int();
s[i].t = read_int();
s[i].a = read_int();
s[i].b = read_int();
}
for (int i=1; i<=nQueries; ++i) {
Q[i].l = read_int();
Q[i].y = read_int();
}
}
void compress() {
for (int i=1; i<=n; ++i) {
T.push_back(s[i].a);
T.push_back(s[i].b);
}
for (int i=1; i<=nQueries; ++i)
T.push_back(Q[i].y);
sort(T.begin(), T.end());
T.resize(unique(T.begin(), T.end()) - T.begin());
#define get_pos(P, x) lower_bound(P.begin(), P.end(), x) - P.begin() + 1
for (int i=1; i<=n; ++i) {
s[i].a = get_pos(T, s[i].a);
s[i].b = get_pos(T, s[i].b);
}
for (int i=1; i<=nQueries; ++i)
Q[i].y = get_pos(T, Q[i].y);
#undef uniq
}
void init() {
for (int i=1; i<=n; ++i) {
store_event[s[i].a].push_back(i);
store_event[s[i].b+1].push_back(-i);
}
for (int i=1; i<=nQueries; ++i) {
q[Q[i].y].push_back(i);
}
for (int i=1; i<=k; ++i) {
++pos[i][-INF];
++pos[i][INF];
interval_set.insert(-INF, INF);
}
}
void add_store(int idx) {
int tmp = ++pos[s[idx].t][s[idx].x];
if (tmp==1) {
auto u = pos[s[idx].t].lower_bound(s[idx].x);
--u;
auto v = pos[s[idx].t].upper_bound(s[idx].x);
// debug(u->first);
// debug(v->first);
interval_set.erase(u->first, v->first);
interval_set.insert(u->first, s[idx].x);
interval_set.insert(s[idx].x, v->first);
}
}
void remove_store(int idx) {
int tmp = --pos[s[idx].t][s[idx].x];
if (!tmp) {
auto u = pos[s[idx].t].lower_bound(s[idx].x);
--u;
auto v = pos[s[idx].t].upper_bound(s[idx].x);
// debug(u->first);
// debug(v->first);
interval_set.erase(u->first, s[idx].x);
interval_set.erase(s[idx].x, v->first);
interval_set.insert(u->first, v->first);
pos[s[idx].t].erase(s[idx].x);
}
}
int bisect(int x) {
int l = 0, r = 2e8;
for (int mid=(l+r)/2; mid!=l && r!=mid; mid=(l+r)/2) {
if (interval_set.get(x-mid-1)>x+mid)
l = mid;
else
r = mid;
}
for (int i=l; i<=r; ++i) {
if (interval_set.get(x-i-1)<=x+i)
return i;
}
return -1;
}
void solve() {
debug(T.size());
for (int i=1; i<=T.size(); ++i) {
for (auto x : store_event[i]) {
if (x>0)
add_store(x);
else
remove_store(-x);
}
for (auto x : q[i])
res[x] = bisect(Q[x].l);
}
for (int i=1; i<=nQueries; ++i)
cout << res[i] << '\n';
}
int main() {
#ifdef GLASSES_GIRL
freopen(FILE_NAME".in", "r", stdin);
freopen(FILE_NAME".out", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
read_input();
compress();
init();
solve();
}
Compilation message
new_home.cpp: In function 'void solve()':
new_home.cpp:261:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1; i<=T.size(); ++i) {
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
84984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
84984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5041 ms |
113088 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5071 ms |
131316 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
84984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
84984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
