#include <bits/stdc++.h>
using namespace std;
#define MXN 300010
#define MXNODES MXN*20
#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif
set<pair<int, int> > segments[MXNODES][2];
int l[MXNODES], r[MXNODES], upto;
void addsegment(int s, int e, pair<int, int> val, int whichone, int curr = 1, int cstart = 0, int cend = 1e8)
{
if (e < cstart || s > cend) return;
if (s <= cstart && cend <= e)
{
segments[curr][whichone].insert(val);
return;
}
int mid = (cstart+cend)/2;
if (e <= mid)
{
if (!l[curr]) l[curr] = ++upto;
addsegment(s, e, val, whichone, l[curr], cstart, mid);
}
else if (s > mid)
{
if (!r[curr]) r[curr] = ++upto;
addsegment(s, e, val, whichone, r[curr], mid+1, cend);
}
else
{
if (!l[curr]) l[curr] = ++upto;
if (!r[curr]) r[curr] = ++upto;
addsegment(s, e, val, whichone, l[curr], cstart, mid);
addsegment(s, e, val, whichone, r[curr], mid+1, cend);
}
}
void removesegment(int s, int e, pair<int, int> val, int whichone, int curr = 1, int cstart = 0, int cend = 1e8)
{
if (e < cstart || s > cend) return;
if (s <= cstart && cend <= e)
{
segments[curr][whichone].erase(val);
return;
}
int mid = (cstart+cend)/2;
if (e <= mid)
{
removesegment(s, e, val, whichone, l[curr], cstart, mid);
}
else if (s > mid)
{
removesegment(s, e, val, whichone, r[curr], mid+1, cend);
}
else
{
removesegment(s, e, val, whichone, l[curr], cstart, mid);
removesegment(s, e, val, whichone, r[curr], mid+1, cend);
}
}
pair<int, int> query(int node, int curr = 1, int cstart = 0, int cend = 1e8)
{
pair<int, int> ans = { 3e8, -2e8 };
if (segments[curr][0].size()) ans.first = segments[curr][0].begin()->first;
if (segments[curr][1].size()) ans.second = segments[curr][1].rbegin()->first;
if (cstart == cend) return ans;
int mid = (cstart+cend)/2;
pair<int, int> child;
if (node <= mid) child = query(node, l[curr], cstart, mid);
else child = query(node, r[curr], mid+1, cend);
ans.first = min(ans.first, child.first);
ans.second = max(ans.second, child.second);
return ans;
}
int n, k, q, x[MXN], t[MXN], a[MXN], b[MXN], amwithshop;
vector<pair<int, int> > events;
set<pair<int, int> > shops[MXN];
pair<int, int> queries[MXN];
int sq[MXN], ans[MXN];
int doQuery(int loc)
{
if (amwithshop != k)
{
return -1;
}
// jdi
auto res = query(loc);
D("%d %d\n", res.first, res.second);
int before = loc-res.first;
int after = res.second-loc;
int ans = max(before, after);
return ans;
}
int main()
{
++upto;
scanf("%d%d%d", &n, &k, &q);
for (int i = 1; i <= k; i++)
{
shops[i].insert({ -2e8, -1 }), shops[i].insert({ 3e8, -2 });
// dumbie stuff
addsegment(-2e8, 0, {-2e8, -1}, 0);
addsegment(0, 3e8, {3e8, -2}, 1);
}
for (int i = 0; i < n; i++)
{
scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
events.emplace_back(i, 0);
events.emplace_back(i, 1);
}
for (int i = 0; i < q; i++)
{
scanf("%d%d", &queries[i].second, &queries[i].first);
}
iota(sq, sq+q, 0);
sort(sq, sq+q, [&](int a, int b) { return queries[a].first < queries[b].first;});
int qupto = 0;
sort(events.begin(), events.end(), [](const pair<int, int> &i, const pair<int, int> &j)
{
int val1 = i.second ? b[i.first] : a[i.first];
int val2 = j.second ? b[j.first] : a[j.first];
return make_pair(val1, i.second) < make_pair(val2, j.second);
});
for (auto f : events)
{
int i = f.first;
int eventType = f.second;
int timeOfEvent = eventType ? b[i]+1 : a[i];
while (qupto < q && queries[sq[qupto]].first < timeOfEvent)
{
// do query
ans[sq[qupto]] = doQuery(queries[sq[qupto]].second);
qupto++;
}
D("\nprocessing %d %d : %d (time: %d)\n", i, eventType, t[i], eventType ? b[i] : a[i]);
if (!eventType) // new thing
{
D("new thing\n");
if (shops[t[i]].size() == 2) amwithshop++;
auto it = shops[t[i]].lower_bound({x[i], i});
auto after = *it;
auto before = *prev(it);
// remove the ranges
int mid = (before.first+after.first)/2;
removesegment(before.first, mid, before, 0);
mid = (before.first+after.first+1)/2;
removesegment(mid, after.first, after, 1);
// add in, then add ranges (4)
shops[t[i]].insert({x[i], i});
mid = (before.first+x[i])/2;
D("adding range first %d %d\n", before.first, mid);
addsegment(before.first, mid, before, 0);
mid = (before.first+x[i]+1)/2;
D("adding range second %d %d\n", mid, x[i]);
addsegment(mid, x[i], { x[i], i }, 1);
mid = (x[i]+after.first)/2;
D("adding range first %d %d\n", x[i], mid);
addsegment(x[i], mid, { x[i], i }, 0);
mid = (x[i]+after.first+1)/2;
D("adding range second %d %d\n", mid, after.first);
addsegment(mid, after.first, after, 1);
}
else // end of thing
{
D("end of thing\n");
shops[t[i]].erase({x[i], i});
auto it = shops[t[i]].lower_bound({x[i], i});
auto after = *it;
auto before = *prev(it);
// remove ranges
int mid = (before.first+x[i])/2;
removesegment(before.first, mid, before, 0);
mid = (before.first+x[i]+1)/2;
removesegment(mid, x[i], { x[i], i }, 1);
mid = (x[i]+after.first)/2;
removesegment(x[i], mid, { x[i], i }, 0);
mid = (x[i]+after.first+1)/2;
removesegment(mid, after.first, after, 1);
// add new ranges
mid = (before.first+after.first)/2;
addsegment(before.first, mid, before, 0);
mid = (before.first+after.first+1)/2;
addsegment(mid, after.first, after, 1);
if (shops[t[i]].size() == 2) amwithshop--;
}
}
while (qupto < q)
{
ans[sq[qupto]] = doQuery(queries[sq[qupto]].second);
qupto++;
}
for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:98: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:108: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:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &queries[i].second, &queries[i].first);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
521 ms |
578104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
521 ms |
578104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5070 ms |
892488 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5075 ms |
820104 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
521 ms |
578104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
521 ms |
578104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
