//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;
struct segment_tree {
int n;
int st[MAX_N*8];
void init(int _n) {
n = _n;
memset(st, 0, sizeof(st));
}
void upd(int pos, int val, int l, int r, int idx) {
if (pos<l || pos>r)
return;
if (l==r) {
st[idx] = val;
return;
}
int mid = (l + r) / 2;
upd(pos, val, l, mid, idx*2);
upd(pos, val, mid+1, r, idx*2+1);
st[idx] = max(st[idx*2], st[idx*2+1]);
}
bool get(int u, int v, int val, int l, int r, int idx) {
if (v<l || u>r)
return true;
if (u<=l && r<=v)
return st[idx]<=val;
int mid = (l + r) / 2;
return get(u, v, val, mid+1, r, idx*2+1) && get(u, v, val, l, mid, idx*2);
}
void upd(int pos, int val) {
upd(pos, val, 1, n, 1);
}
bool get(int u, int v, int val) {
return get(u, v, val, 1, n, 1);
}
};
struct store {
int x, t, a, b;
};
struct query {
int l, y;
};
int n, k, nQueries, res[MAX_N];
vector<int> T, L, store_event[MAX_N*3], q[MAX_N*3];
store s[MAX_N];
query Q[MAX_N];
map<int, int> pos[MAX_N*3];
multiset<int> g[MAX_N*2];
segment_tree tr;
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() {
L.push_back(-INF);
L.push_back(INF);
for (int i=1; i<=n; ++i) {
T.push_back(s[i].a);
T.push_back(s[i].b+1);
L.push_back(s[i].x);
}
for (int i=1; i<=nQueries; ++i) {
T.push_back(Q[i].y);
L.push_back(Q[i].l);
}
#define uniq(P) {sort(P.begin(), P.end()); P.resize(unique(P.begin(), P.end()) - P.begin());}
uniq(T);
uniq(L);
#undef uniq
#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+1);
s[i].x = get_pos(L, s[i].x);
}
for (int i=1; i<=nQueries; ++i) {
Q[i].y = get_pos(T, Q[i].y);
// Q[i].l = get_pos(L, Q[i].l);
}
#undef uniq
}
void init() {
tr.init(L.size());
for (int i=1; i<=n; ++i) {
store_event[s[i].a].push_back(i);
store_event[s[i].b].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][1];
++pos[i][L.size()];
g[1].insert(L.size());
}
for (int i=1; i<=L.size(); ++i)
g[i].insert(0);
tr.upd(1, L.size());
}
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);
g[u->first].erase(g[u->first].find(v->first));
g[u->first].insert(s[idx].x);
g[s[idx].x].insert(v->first);
tr.upd(u->first, *g[u->first].rbegin());
// cerr << u->first << ' ' << *g[u->first].rbegin() << '\n';
tr.upd(s[idx].x, *g[s[idx].x].rbegin());
// cerr << s[idx].x << ' ' << *g[s[idx].x].rbegin() << '\n';
}
}
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);
g[u->first].erase(g[u->first].find(s[idx].x));
g[s[idx].x].erase(g[s[idx].x].find(v->first));
g[u->first].insert(v->first);
tr.upd(u->first, *g[u->first].rbegin());
// cerr << u->first << ' ' << *g[u->first].rbegin() << '\n';
tr.upd(s[idx].x, *g[s[idx].x].rbegin());
// cerr << s[idx].x << ' ' << *g[s[idx].x].rbegin() << '\n';
pos[s[idx].t].erase(s[idx].x);
}
}
int get_id(int x) {
return upper_bound(L.begin(), L.end(), x) - L.begin();
}
int bisect(int x) {
int l = 0, r = 1e8;
for (int mid=(l+r)/2; mid!=l && r!=mid; mid=(l+r)/2) {
if (tr.get(1, get_id(x-mid-1), get_id(x+mid)))
r = mid;
else
l = mid;
}
for (int i=l; i<=r; ++i) {
if (tr.get(1, get_id(x-i-1), get_id(x+i)))
return i;
}
return -1;
}
void solve() {
int tmp = 0;
for (int i=1; i<=nQueries; ++i)
tmp = max(tmp, Q[i].y);
for (int i=1; i<=tmp; ++i) {
for (auto x : store_event[i]) {
if (x>0)
add_store(x);
else
remove_store(-x);
}
// debug(tr.get(1, 2, 4));
for (auto x : q[i])
res[x] = bisect(Q[x].l);
}
// debug(tr.get())
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 init()':
new_home.cpp:161:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1; i<=L.size(); ++i)
~^~~~~~~~~~
new_home.cpp: In function 'void solve()':
new_home.cpp:235:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i=1; i<=nQueries; ++i)
^~~
new_home.cpp:238:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i=1; i<=tmp; ++i) {
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
122488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
122488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
758 ms |
184624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
885 ms |
184376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
122488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
122488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
