#include <bits/stdc++.h>
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 500000;
int x[N], t[N], a[N], b[N], l[N], y[N];
int ans[N];
vector <pii> values;
struct segtree {
vector <int> seg;
int n, k, a, b, t;
segtree() { }
segtree(int n, int t) : n(n), t(t) {
if (t)
seg.resize(4*n+1, INT_MAX);
else
seg.resize(4*n+1, -1);
}
int operador (int x, int y) {
return t ? min(x, y) : max(x, y);
}
void update (int r, int i, int j) {
if (i > b or j < a) return ;
if (i >= a and j <= b) {
seg[r] = k;
return ;
}
int mid = (i + j) / 2;
update (r*2, i, mid);
update (r*2+1, mid+1, j);
seg[r] = operador(seg[r*2], seg[r*2+1]);
// if (t == 1) cout << r << " " << i << " " << j << ": " << seg[r] << endl;
}
int query_left (int r, int i, int j) {
if (i > b or j < a) return -1;
int mid = (i + j) / 2;
if (i >= a and j <= b) {
if (seg[r] < k) return -1;
if (i == j) return i;
if (seg[r*2] >= k) return query_left(r*2, i, mid);
return query_left(r*2+1, mid+1, j);
}
int l = query_left(r*2, i, mid);
return l == -1 ? query_left(r*2+1, mid+1, j) : l;
}
int query_right (int r, int i, int j) {
// printf("query_right i %d j %d a %d b %d segr %d\n", i, j, a, b, seg[r]);
if (i > b or j < a) return -1;
int mid = (i + j) / 2;
if (i >= a and j <= b) {
if (seg[r] > k) return -1;
if (i == j) return i;
if (seg[r*2+1] <= k) return query_right(r*2+1, mid+1, j);
return query_right(r*2, i, mid);
}
int l = query_right(r*2+1, mid+1, j);
return l == -1 ? query_right(r*2, i, mid) : l;
}
void update (int id, int val) {
// printf("update \t st %d id %d x %d val %d\n", t, id, x[id], val);
a = b = lower_bound(values.begin(), values.end(), mp(x[id], id)) - values.begin();
// printf("\t a %d b %d\n", a, b);
k = val;
update (1, 0, n-1);
}
int query_left (int pos, int val) {
a = 0;
b = upper_bound(values.begin(), values.end(), mp(pos, INF)) - values.begin();
k = val;
return query_left (1, 0, n-1);
}
int query_right (int pos, int val) {
a = lower_bound(values.begin(), values.end(), mp(pos, -1)) - values.begin();
b = n-1;
k = val;
// cout << a << " " << b << " " << k << " " << seg[1] << endl;
return query_right(1, 0, n-1);
}
} st[2];
set <pii> active[N];
set<pii>::iterator it;
//left update 0
//right update 1
void add (int left, int right) {
if (x[left] == x[right]) {
st[0].update(left, x[left]);
st[1].update(right, x[right]);
return ;
}
int mid = (x[left] + x[right]) / 2;
st[0].update(left, mid);
st[1].update(right, mid+1);
}
void remove (int left, int right) {
st[0].update(left, -1);
st[1].update(right, INF);
}
int main (void) {
int n, k, q;
scanf("%d %d %d", &n, &k, &q);
vector < tuple<int, int, int> > evt;
for (int i = 0; i < n; i++) {
scanf("%d %d %d %d", x+i, t+i, a+i, b+i);
evt.eb(a[i], 0, i);
evt.eb(b[i], 2, i);
values.eb(x[i], i);
}
for (int i = 0; i < q; i++) {
scanf("%d %d", l+i, y+i);
// cout << l[i] << " " << y[i] << endl;
evt.eb(y[i], 1, i);
}
sort(evt.begin(), evt.end());
sort(values.begin(), values.end());
// for (int i = 0; i < n; i++)
// printf("%d: %d %d\n", i, values[i].fi, values[i].se);
// printf("------------\n");
st[0] = segtree(n, 0); //maximo
st[1] = segtree(n, 1); //minimo
int cnt = 0;
for (int i = 0; i < evt.size(); i++) {
int coord, tipo, id; tie(coord, tipo, id) = evt[i];
// cout << coord << " " << tipo << " " << id << endl;
if (!tipo) { //inserir
// printf("add t %d x %d\n", t[id], x[id]);
if (active[t[id]].empty()) {
st[0].update(id, INF);
st[1].update(id, -1);
active[t[id]].insert(mp(x[id], id));
cnt++;
continue;
}
it = active[t[id]].lower_bound(mp(x[id], id));
if (it != active[t[id]].end()) add(id, it->se);
else st[0].update(id, INF);
if (it != active[t[id]].begin()) {
it--;
add(it->se, id);
} else st[1].update(id, -1);
active[t[id]].insert(mp(x[id], id));
} else if (tipo == 2) {
// printf("rem t %d x %d\n", t[id], x[id]);
it = active[t[id]].lower_bound(mp(x[id], id+1));
if (it != active[t[id]].end()) remove(id, it->se);
else st[0].update(id, -1);
it = active[t[id]].lower_bound(mp(x[id], id));
if (it != active[t[id]].begin()) {
it--;
remove(it->se, id);
} else st[1].update(id, INF);
active[t[id]].erase(mp(x[id], id));
if (active[t[id]].empty()) {
cnt--;
continue;
}
int l = -1, r = INF;
it = active[t[id]].lower_bound(mp(x[id], id+1));
if (it != active[t[id]].end()) r = it->se;
if (it != active[t[id]].begin()) {
it--;
l = it->se;
}
if (l == -1) st[1].update(r, -1);
else if (r == INF) st[0].update(l, INF);
else add(l, r);
} else { //query
// printf("query x %d\n", l[id]);
int x = st[0].query_left(l[id], coord);
int y = st[1].query_right(l[id], coord);
// printf("x %d y %d\n", x, y);
if (x == -1 and y == -1) ans[id] = -1;
else if (y == -1) ans[id] = l[id] - values[x].fi;
else if (x == -1) ans[id] = values[y].fi - l[id];
else ans[id] = max(values[y].fi -l[id], l[id] - values[x].fi);
if (cnt != k) ans[id] = -1;
// cout << ans[id] << endl;
}
}
for (int i = 0; i < q; i++)
printf("%d\n", ans[i]);
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:134:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < evt.size(); i++) {
~~^~~~~~~~~~~~
new_home.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &k, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", x+i, t+i, a+i, b+i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", l+i, y+i);
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23912 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24020 KB |
Output is correct |
| 4 |
Incorrect |
23 ms |
24056 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23912 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24020 KB |
Output is correct |
| 4 |
Incorrect |
23 ms |
24056 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2413 ms |
71304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3069 ms |
71304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23912 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24020 KB |
Output is correct |
| 4 |
Incorrect |
23 ms |
24056 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23912 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24020 KB |
Output is correct |
| 4 |
Incorrect |
23 ms |
24056 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
