#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, q, k, i, x, t, a, b, ans, MXM;
bool ok;
pair<pair<int, int>, pair<int, int> > shops[300005];
struct Node {
int val;
Node *l, *r;
Node(int x) : val(x), l(nullptr), r(nullptr) {}
Node(Node *ll, Node *rr) {
val = 0;
l = ll;
r = rr;
if (l) val += l->val;
if (r) val += r->val;
}
Node(Node *cp) : val(cp->val), l(cp->l), r(cp->r) {};
};
vector<Node*> heads[300005];
vector<int> times[300005];
Node *Update(Node *node, int pos, int val, int l=1, int r=MXM) {
if (l == r) return new Node(node->val+val);
int mid = (l+r)/2;
if (pos <= mid) {
if (node->l == nullptr) node->l = new Node(0);
return new Node(Update(node->l, pos, val, l, mid), node->r);
}
else {
if (node->r == nullptr) node->r = new Node(0);
return new Node(node->l, Update(node->r, pos, val, mid+1, r));
}
}
int Query(Node *node, int from, int to, int l=1, int r=MXM) {
if (node == nullptr) return 0;
if (from == l && to == r) return node->val;
int mid = (l+r)/2;
if (to <= mid) return Query(node->l, from, to, l, mid);
else if (from > mid) return Query(node->r, from, to, mid+1, r);
else return Query(node->l, from, mid, l, mid) + Query(node->r, mid+1, to, mid+1, r);
}
int Walk(Node *node, int kval, int l=1, int r=MXM) {
if (l == r) return l;
int mid = (l+r)/2;
if (node->l == nullptr) return Walk(node->r, kval, mid+1, r);
else if ((node->l)->val < kval) return Walk(node->r, kval-(node->l)->val, mid+1, r);
else return Walk(node->l, kval, l, mid);
}
int main() {
scanf("%d%d%d", &n, &k, &q);
MXM = 0;
for (i=0; i < n; ++i) {
scanf("%d%d%d%d", &x, &t, &a, &b);
MXM = max(MXM, x+5);
shops[2*i] = make_pair(make_pair(a, 1), make_pair(x, t));
shops[2*i+1] = make_pair(make_pair(b+1, -1), make_pair(x, t));
}
sort(shops, shops+2*n);
for (i=1; i <= k; ++i) {
heads[i].push_back(new Node(0));
times[i].push_back(0);
}
for (i=0; i < 2*n; ++i) {
t = shops[i].Y.Y;
x = shops[i].Y.X;
a = shops[i].X.X;
b = shops[i].X.Y;
heads[t].push_back(Update(heads[t].back(), x, b));
times[t].push_back(a);
}
while(q--) {
scanf("%d%d", &a, &b);
ok = true;
ans = 0;
for (i=1; i <= k; ++i) {
t = prev(upper_bound(times[i].begin(), times[i].end(), b))-times[i].begin();
if (Query(heads[i][t], 1, MXM) == 0) {
ok = false;
break;
}
if (Query(heads[i][t], a, a) == 0) {
int d1 = 100000005;
int d2 = 100000005;
int q1 = 0;
if (a > 1) q1 = Query(heads[i][t], 1, a-1);
if (q1 > 0) d1 = a-Walk(heads[i][t], q1);
int q2 = Query(heads[i][t], a+1, MXM);
if (q2 > 0) d2 = Walk(heads[i][t], q1+1)-a;
d1 = min(d1, d2);
ans = max(ans, d1);
}
}
if (!ok) printf("-1\n");
else printf("%d\n", ans);
}
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d%d%d", &n, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d%d%d%d", &x, &t, &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
14292 KB |
Output is correct |
2 |
Correct |
6 ms |
14404 KB |
Output is correct |
3 |
Correct |
6 ms |
14292 KB |
Output is correct |
4 |
Correct |
6 ms |
14404 KB |
Output is correct |
5 |
Correct |
7 ms |
14532 KB |
Output is correct |
6 |
Correct |
9 ms |
15372 KB |
Output is correct |
7 |
Correct |
8 ms |
15444 KB |
Output is correct |
8 |
Correct |
9 ms |
15408 KB |
Output is correct |
9 |
Correct |
9 ms |
15500 KB |
Output is correct |
10 |
Correct |
10 ms |
15304 KB |
Output is correct |
11 |
Correct |
8 ms |
15316 KB |
Output is correct |
12 |
Correct |
8 ms |
15316 KB |
Output is correct |
13 |
Correct |
8 ms |
15316 KB |
Output is correct |
14 |
Correct |
11 ms |
15316 KB |
Output is correct |
15 |
Correct |
17 ms |
15504 KB |
Output is correct |
16 |
Correct |
20 ms |
15444 KB |
Output is correct |
17 |
Correct |
12 ms |
15444 KB |
Output is correct |
18 |
Correct |
14 ms |
15444 KB |
Output is correct |
19 |
Correct |
17 ms |
15364 KB |
Output is correct |
20 |
Correct |
11 ms |
15452 KB |
Output is correct |
21 |
Correct |
17 ms |
15436 KB |
Output is correct |
22 |
Correct |
18 ms |
15508 KB |
Output is correct |
23 |
Correct |
16 ms |
15492 KB |
Output is correct |
24 |
Correct |
16 ms |
15480 KB |
Output is correct |
25 |
Correct |
12 ms |
15452 KB |
Output is correct |
26 |
Correct |
9 ms |
15316 KB |
Output is correct |
27 |
Correct |
9 ms |
14548 KB |
Output is correct |
28 |
Correct |
9 ms |
15316 KB |
Output is correct |
29 |
Correct |
8 ms |
15316 KB |
Output is correct |
30 |
Correct |
8 ms |
15072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
14292 KB |
Output is correct |
2 |
Correct |
6 ms |
14404 KB |
Output is correct |
3 |
Correct |
6 ms |
14292 KB |
Output is correct |
4 |
Correct |
6 ms |
14404 KB |
Output is correct |
5 |
Correct |
7 ms |
14532 KB |
Output is correct |
6 |
Correct |
9 ms |
15372 KB |
Output is correct |
7 |
Correct |
8 ms |
15444 KB |
Output is correct |
8 |
Correct |
9 ms |
15408 KB |
Output is correct |
9 |
Correct |
9 ms |
15500 KB |
Output is correct |
10 |
Correct |
10 ms |
15304 KB |
Output is correct |
11 |
Correct |
8 ms |
15316 KB |
Output is correct |
12 |
Correct |
8 ms |
15316 KB |
Output is correct |
13 |
Correct |
8 ms |
15316 KB |
Output is correct |
14 |
Correct |
11 ms |
15316 KB |
Output is correct |
15 |
Correct |
17 ms |
15504 KB |
Output is correct |
16 |
Correct |
20 ms |
15444 KB |
Output is correct |
17 |
Correct |
12 ms |
15444 KB |
Output is correct |
18 |
Correct |
14 ms |
15444 KB |
Output is correct |
19 |
Correct |
17 ms |
15364 KB |
Output is correct |
20 |
Correct |
11 ms |
15452 KB |
Output is correct |
21 |
Correct |
17 ms |
15436 KB |
Output is correct |
22 |
Correct |
18 ms |
15508 KB |
Output is correct |
23 |
Correct |
16 ms |
15492 KB |
Output is correct |
24 |
Correct |
16 ms |
15480 KB |
Output is correct |
25 |
Correct |
12 ms |
15452 KB |
Output is correct |
26 |
Correct |
9 ms |
15316 KB |
Output is correct |
27 |
Correct |
9 ms |
14548 KB |
Output is correct |
28 |
Correct |
9 ms |
15316 KB |
Output is correct |
29 |
Correct |
8 ms |
15316 KB |
Output is correct |
30 |
Correct |
8 ms |
15072 KB |
Output is correct |
31 |
Execution timed out |
5065 ms |
162020 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
59 ms |
38508 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
58 ms |
38872 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
14292 KB |
Output is correct |
2 |
Correct |
6 ms |
14404 KB |
Output is correct |
3 |
Correct |
6 ms |
14292 KB |
Output is correct |
4 |
Correct |
6 ms |
14404 KB |
Output is correct |
5 |
Correct |
7 ms |
14532 KB |
Output is correct |
6 |
Correct |
9 ms |
15372 KB |
Output is correct |
7 |
Correct |
8 ms |
15444 KB |
Output is correct |
8 |
Correct |
9 ms |
15408 KB |
Output is correct |
9 |
Correct |
9 ms |
15500 KB |
Output is correct |
10 |
Correct |
10 ms |
15304 KB |
Output is correct |
11 |
Correct |
8 ms |
15316 KB |
Output is correct |
12 |
Correct |
8 ms |
15316 KB |
Output is correct |
13 |
Correct |
8 ms |
15316 KB |
Output is correct |
14 |
Correct |
11 ms |
15316 KB |
Output is correct |
15 |
Correct |
17 ms |
15504 KB |
Output is correct |
16 |
Correct |
20 ms |
15444 KB |
Output is correct |
17 |
Correct |
12 ms |
15444 KB |
Output is correct |
18 |
Correct |
14 ms |
15444 KB |
Output is correct |
19 |
Correct |
17 ms |
15364 KB |
Output is correct |
20 |
Correct |
11 ms |
15452 KB |
Output is correct |
21 |
Correct |
17 ms |
15436 KB |
Output is correct |
22 |
Correct |
18 ms |
15508 KB |
Output is correct |
23 |
Correct |
16 ms |
15492 KB |
Output is correct |
24 |
Correct |
16 ms |
15480 KB |
Output is correct |
25 |
Correct |
12 ms |
15452 KB |
Output is correct |
26 |
Correct |
9 ms |
15316 KB |
Output is correct |
27 |
Correct |
9 ms |
14548 KB |
Output is correct |
28 |
Correct |
9 ms |
15316 KB |
Output is correct |
29 |
Correct |
8 ms |
15316 KB |
Output is correct |
30 |
Correct |
8 ms |
15072 KB |
Output is correct |
31 |
Execution timed out |
5065 ms |
162020 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
14292 KB |
Output is correct |
2 |
Correct |
6 ms |
14404 KB |
Output is correct |
3 |
Correct |
6 ms |
14292 KB |
Output is correct |
4 |
Correct |
6 ms |
14404 KB |
Output is correct |
5 |
Correct |
7 ms |
14532 KB |
Output is correct |
6 |
Correct |
9 ms |
15372 KB |
Output is correct |
7 |
Correct |
8 ms |
15444 KB |
Output is correct |
8 |
Correct |
9 ms |
15408 KB |
Output is correct |
9 |
Correct |
9 ms |
15500 KB |
Output is correct |
10 |
Correct |
10 ms |
15304 KB |
Output is correct |
11 |
Correct |
8 ms |
15316 KB |
Output is correct |
12 |
Correct |
8 ms |
15316 KB |
Output is correct |
13 |
Correct |
8 ms |
15316 KB |
Output is correct |
14 |
Correct |
11 ms |
15316 KB |
Output is correct |
15 |
Correct |
17 ms |
15504 KB |
Output is correct |
16 |
Correct |
20 ms |
15444 KB |
Output is correct |
17 |
Correct |
12 ms |
15444 KB |
Output is correct |
18 |
Correct |
14 ms |
15444 KB |
Output is correct |
19 |
Correct |
17 ms |
15364 KB |
Output is correct |
20 |
Correct |
11 ms |
15452 KB |
Output is correct |
21 |
Correct |
17 ms |
15436 KB |
Output is correct |
22 |
Correct |
18 ms |
15508 KB |
Output is correct |
23 |
Correct |
16 ms |
15492 KB |
Output is correct |
24 |
Correct |
16 ms |
15480 KB |
Output is correct |
25 |
Correct |
12 ms |
15452 KB |
Output is correct |
26 |
Correct |
9 ms |
15316 KB |
Output is correct |
27 |
Correct |
9 ms |
14548 KB |
Output is correct |
28 |
Correct |
9 ms |
15316 KB |
Output is correct |
29 |
Correct |
8 ms |
15316 KB |
Output is correct |
30 |
Correct |
8 ms |
15072 KB |
Output is correct |
31 |
Execution timed out |
5065 ms |
162020 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |