#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 6e5 + 5, inf = 1e8;
int n, k, q, cnt, m;
int mark[maxn], ans[maxn];
vector<int> nen;
array<int, 3> qr[maxn];
array<int, 4> store[maxn];
vector<array<int, 5>> seg;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> bound_right;
multiset<int> type[maxn], segment[maxn];
int st[4 * maxn];
void upd(int pos, int id = 1, int l = 1, int r = m)
{
if (l == r) return void(st[id] = (segment[l].size() ? *segment[r].rbegin() : inf));
int mid = (l + r) / 2;
if (pos <= mid) upd(pos, id * 2, l, mid);
else upd(pos, id * 2 + 1, mid + 1, r);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
int get(int pos, int id = 1, int l = 1, int r = m)
{
if (l == r) return st[id];
int mid = (l + r) / 2;
if (pos <= mid) return get(pos, id * 2, l, mid);
return max(st[id * 2], get(pos, id * 2 + 1, mid + 1, r));
}
void add_seg(int l, int r)
{
// cerr << l << " " << r << " add\n";
l = upper_bound(all(nen), l) - nen.begin();
segment[l].emplace(r);
upd(l);
}
void del_seg(int l, int r)
{
// cerr << l << " " << r << " del\n";
l = upper_bound(all(nen), l) - nen.begin();
// cerr << l << " ??\n";
segment[l].erase(segment[l].find(r));
upd(l);
}
set<int> naww;
void add(int id)
{
auto [x, t, l, r] = store[id];
l = 1, r = inf;
auto it = type[t].lower_bound(x);
if (it != type[t].end()) r = *it - 1;
if (it != type[t].begin()) l = *prev(it) + 1;
type[t].emplace(x);
del_seg(l, r);
add_seg(l, x - 1);
add_seg(x + 1, r);
}
void del(int id)
{
auto [x, t, l, r] = store[id];
l = 1, r = inf;
auto it = type[t].lower_bound(x);
if (next(it) != type[t].end()) r = *next(it) - 1;
if (it != type[t].begin()) l = *prev(it) + 1;
type[t].erase(it);
del_seg(l, x - 1);
del_seg(x + 1, r);
add_seg(l, r);
}
int get_ans(int x)
{
int l = 0, r = inf, ans = -1;
while (l <= r)
{
int mid = (l + r) / 2;
int lx = max(1ll, x - mid), rx = min(inf, x + mid);
int pos = upper_bound(all(nen), lx) - nen.begin();
if (get(pos) >= rx) l = mid + 1;
else ans = mid, r = mid - 1;
}
return ans;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("test.inp", "r", stdin);
// freopen("AC.out", "w", stdout);
cin >> n >> k >> q;
nen = {1};
for (int i = 1; i <= n; i++)
{
int x, t, a, b;
cin >> x >> t >> a >> b;
store[i] = {x, t, a, b};
nen.emplace_back(x + 1);
}
for (int i = 1, x, t; i <= q; i++)
cin >> x >> t,
qr[i] = {t, x, i};
// nen.emplace_back(x);
sort(all(nen));
nen.resize(unique(all(nen)) - nen.begin());
m = nen.size();
for (int i = 1; i <= n; i++)
{
auto [x, t, l, r] = store[i];
seg.push_back({x, t, l, r, i});
}
sort(all(seg),[](array<int, 5> x, array<int, 5> y)
{
if (x[2] != y[2]) return x[2] < y[2];
return x[3] < y[3];
});
for (int i = 1; i <= k; i++)
segment[1].emplace(inf);
for (int i = 1; i <= m; i++) upd(i);
sort(qr + 1, qr + q + 1);
memset(ans, -1, sizeof ans);
for (int i = 1, it = 0; i <= q; i++)
{
auto [time, pos, id] = qr[i];
while (it < seg.size() && seg[it][2] <= time)
add(seg[it][4]),
bound_right.emplace(seg[it][3], seg[it][4]),
it++;
while (bound_right.size() && bound_right.top().first < time)
del(bound_right.top().second),
bound_right.pop();
// if (i == 3) {for (int j : naww) cout << j << " dontplay\n";}
ans[id] = get_ans(pos);
}
for (int i = 1; i <= q; i++)
cout << ans[i] << "\n";
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:133:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 5> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | while (it < seg.size() && seg[it][2] <= time)
| ~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
63580 KB |
Output is correct |
| 2 |
Correct |
21 ms |
63580 KB |
Output is correct |
| 3 |
Correct |
20 ms |
63580 KB |
Output is correct |
| 4 |
Incorrect |
21 ms |
63580 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
63580 KB |
Output is correct |
| 2 |
Correct |
21 ms |
63580 KB |
Output is correct |
| 3 |
Correct |
20 ms |
63580 KB |
Output is correct |
| 4 |
Incorrect |
21 ms |
63580 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1176 ms |
140180 KB |
Output is correct |
| 2 |
Correct |
1899 ms |
148372 KB |
Output is correct |
| 3 |
Correct |
1161 ms |
165048 KB |
Output is correct |
| 4 |
Correct |
1225 ms |
155528 KB |
Output is correct |
| 5 |
Correct |
1981 ms |
147816 KB |
Output is correct |
| 6 |
Correct |
1839 ms |
148852 KB |
Output is correct |
| 7 |
Correct |
1177 ms |
165336 KB |
Output is correct |
| 8 |
Correct |
1125 ms |
155924 KB |
Output is correct |
| 9 |
Correct |
1253 ms |
152464 KB |
Output is correct |
| 10 |
Correct |
1836 ms |
149936 KB |
Output is correct |
| 11 |
Correct |
1328 ms |
148364 KB |
Output is correct |
| 12 |
Correct |
1369 ms |
149644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1735 ms |
137448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
63580 KB |
Output is correct |
| 2 |
Correct |
21 ms |
63580 KB |
Output is correct |
| 3 |
Correct |
20 ms |
63580 KB |
Output is correct |
| 4 |
Incorrect |
21 ms |
63580 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
63580 KB |
Output is correct |
| 2 |
Correct |
21 ms |
63580 KB |
Output is correct |
| 3 |
Correct |
20 ms |
63580 KB |
Output is correct |
| 4 |
Incorrect |
21 ms |
63580 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
