#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(i, s, e) for (ll i = (ll)s; i < e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= e; i++)
#define TRAV(e, a) for (const auto &e : a)
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl;
template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &out, const T &obj) {
out << "[";
for (auto it = obj.begin(); it != obj.end(); it++) {
out << &", "[2 * (it == obj.begin())] << *it;
}
return out << "]";
}
template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
return out << "(" << obj.first << ", " << obj.second << ")";
}
struct query {
ll op, x, t, y, id;
};
ostream &operator<<(ostream &out, const query &obj) {
return out << vec<ll>{obj.op, obj.x, obj.t, obj.y, obj.id};
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n, k, q;
cin >> n >> k >> q;
if (k <= 400) {
vec<query> queries;
queries.reserve(2 * n + q);
FOR(i, 0, n) {
ll x, t, a, b;
cin >> x >> t >> a >> b;
queries.push_back({0, x, t, a, i});
queries.push_back({1, x, t, b + 1, i});
}
FOR(i, 0, q) {
ll l, y;
cin >> l >> y;
queries.push_back({2, l, -1, y, n + i});
}
sort(all(queries),
[&](const query &o1, const query &o2) {
return (o1.y == o2.y) ? o1.op < o2.op : o1.y < o2.y;
});
vec<indexed_set<pll>> ss(k + 1);
TRAV(e, queries) {
if (e.op == 0) {
ss[e.t].insert({e.x, e.id});
} else if (e.op == 1) {
ss[e.t].erase({e.x, e.id});
} else if (e.op == 2) {
ll ans = 0;
CFOR(i, 1, k) {
ll mn = INT_MAX;
auto it = ss[i].lower_bound({e.x, INT_MIN});
if (it != ss[i].end()) mn = min(mn, it->first - e.x);
if (it != ss[i].begin())
mn = min(mn, e.x - prev(it)->first);
ans = max(ans, mn);
}
cout << (ans == INT_MAX ? -1 : ans) << "\n";
}
}
} else {
assert(false);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
452 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
452 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
452 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
452 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
