// When they saw the star, they were overjoyed. On coming to the house,
// they saw the child with his mother Mary, and they bowed down and
// worhipped him. Then they opened their treasures and presented him with
// gifts of gold, frankincense and myrrh.
// Matthew 2:10-11
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif
#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 300005
struct store {
int x, t, a, b;
bool operator< (const store& o) const {
return x < o.x;
}
};
struct qry {
int l, y, id;
bool operator< (const qry& o) const {
return y < o.y;
}
};
int n, k, q;
store stores[MAXN];
vector<store> grp[MAXN];
qry qrys[MAXN];
vii dis;
set<ii> st;
int ans[MAXN];
void insert(int x, int y) {
debug(" -> %d %d\n", x, y);
if (st.empty()) {
st.insert(MP(x, y));
return;
}
auto it = prev(st.upper_bound(MP(x, INF)));
if (it -> SE >= y) {
return;
}
if (it -> FI == x) {
st.erase(it);
}
it = next(st.insert(MP(x, y)).FI);
while (it != st.end() && it -> SE <= y) {
it = st.erase(it);
}
return;
}
int main() {
int _t = 1;
//scanf("%d", &_t);
while (_t--) {
scanf("%d%d%d", &n, &k, &q);
REP (i, 0, n) {
int x, t, a, b; scanf("%d%d%d%d", &x, &t, &a, &b);
x *= 2;
stores[i] = (store) {x, t, a, b};
dis.pb(MP(a, i));
dis.pb(MP(b, i + n));
}
REP (i, 0, q) {
int l, y; scanf("%d%d", &l, &y);
l *= 2;
qrys[i] = (qry) {l, y, i};
dis.pb(MP(y, i + 2 * n));
}
sort(ALL(dis));
int prv = -1, sze = 0;
for (auto [a, b] : dis) {
if (a != prv) {
sze++;
prv = a;
}
if (b < n) {
stores[b].a = sze - 1;
} else if (b < 2 * n) {
stores[b - n].b = sze - 1;
} else {
qrys[b - 2 * n].y = sze - 1;
}
}
sort(stores, stores + n);
sort(qrys, qrys + q);
REP (i, 0, n) {
grp[stores[i].t].pb(stores[i]);
}
REP (i, 1, k + 1) {
assert(!grp[i].empty());
insert(-INF, grp[i][0].x);
REP (j, 0, grp[i].size()) {
insert(grp[i][j].x,
j + 1 == grp[i].size() ? INF : grp[i][j + 1].x);
}
}
for (auto [a, b] : st) {
debug("%d %d\n", a, b);
}
auto it = st.begin();
REP (i, 0, q) {
while (next(it) != st.end() &&
(it -> SE + next(it) -> FI) / 2 < qrys[i].l) {
it = next(it);
}
ans[qrys[i].id] = min(it -> SE - qrys[i].l, qrys[i].l - it -> FI);
}
REP (i, 0, q) {
printf("%d\n", ans[i] / 2);
}
}
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:14:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<store>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
124 | REP (j, 0, grp[i].size()) {
| ~~~~~~~~~~~~~~~~~~~
new_home.cpp:124:4: note: in expansion of macro 'REP'
124 | REP (j, 0, grp[i].size()) {
| ^~~
new_home.cpp:126:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<store>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | j + 1 == grp[i].size() ? INF : grp[i][j + 1].x);
| ~~~~~~^~~~~~~~~~~~~~~~
new_home.cpp:129:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
129 | for (auto [a, b] : st) {
| ^~~~~~
new_home.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d%d%d", &n, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:89:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | int x, t, a, b; scanf("%d%d%d%d", &x, &t, &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:96:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | int l, y; scanf("%d%d", &l, &y);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7244 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7244 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7244 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7244 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
395 ms |
34248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
334 ms |
33472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7244 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7244 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7244 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7244 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
