#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>
using namespace std;
const int MAXN = 300000;
const int MAXI = 1048576;
const int INF = 100000000;
int n, k, q, bp;
vector<int> com;
inline int idx(int x)
{
return lower_bound(com.begin(), com.end(), x) - com.begin();
}
struct eve1
{
int t, x, d;
bool operator <(const eve1 &e) const
{
return t != e.t ? t < e.t : d > e.d;
}
};
struct ent1
{
int c, l, lt, r, rt;
};
vector<eve1> arr1;
map<int, ent1> loc1[MAXN + 10];
// add : t time, p = 1, [x -> y] loc, d origin
// query: t time, p = 2, x loc, y idx, d = -1
// sub : t time, p = 3, [x -> y] loc, d origin
struct eve2
{
int t, p, x, y, d;
bool operator <(const eve2 &e) const
{
return t != e.t ? t < e.t : p < e.p;
}
};
vector<eve2> arr2;
void add_seg(int t, int t2, int x, int y)
{
if(t > t2 || x == y)
return;
int nx = bp + idx(min(x, y));
int ny = bp + idx(max(x, y) + 1) - 1;
if(nx > ny)
return;
arr2.push_back({ t, 1, nx, ny, x });
arr2.push_back({ t2, 3, nx, ny, x });
}
multiset<int> mem2[MAXI + 10];
void add(const eve2 &e)
{
int x = e.x;
int y = e.y;
while(x < y)
{
if(x % 2 == 1)
{
if(e.p == 1)
mem2[x].insert(e.d);
else
mem2[x].erase(mem2[x].find(e.d));
x++;
}
if(y % 2 == 0)
{
if(e.p == 1)
mem2[y].insert(e.d);
else
mem2[y].erase(mem2[y].find(e.d));
y--;
}
x /= 2;
y /= 2;
}
if(x == y)
{
if(e.p == 1)
mem2[x].insert(e.d);
else
mem2[x].erase(mem2[x].find(e.d));
}
}
int get(int p)
{
int r = 0;
int x = bp + idx(p);
while(x)
{
auto it = mem2[x].lower_bound(p);
if(it != mem2[x].end())
r = max(r, *it - p);
if(it != mem2[x].begin())
r = max(r, p - *prev(it));
x /= 2;
}
return r;
}
vector<pair<int, int>> can;
int ans[MAXN + 10];
int main()
{
//freopen("in", "r", stdin);
//freopen("out", "w", stdout);
scanf("%d%d%d", &n, &k, &q);
for(int i = 0; i < n; i++)
{
int x, t, a, b;
scanf("%d%d%d%d", &x, &t, &a, &b);
arr1.push_back({ a, x, t });
arr1.push_back({ b, x, -t });
}
for(int i = 0; i < q; i++)
{
int l, y;
scanf("%d%d", &l, &y);
arr2.push_back({ y, 2, l, i, -1 });
com.push_back(l);
}
sort(com.begin(), com.end());
com.erase(unique(com.begin(), com.end()), com.end());
for(bp = 1; bp < (int)com.size(); bp *= 2);
sort(arr1.begin(), arr1.end());
int cur, cnt = 0;
for(eve1 &e : arr1)
{
if(e.d > 0)
{
if(loc1[e.d].size() == 0)
{
cnt++;
if(cnt == k)
cur = e.t;
}
auto it = loc1[e.d].find(e.x);
if(it != loc1[e.d].end())
{
it->second.c++;
continue;
}
it = loc1[e.d].insert({ e.x, { 1, 1, e.t, INF, e.t } }).first;
ent1 &p = it->second;
if(it != loc1[e.d].begin())
{
int x = prev(it)->first;
ent1 &q = prev(it)->second;
add_seg(q.rt, e.t - 1, x, q.r);
q.rt = e.t;
q.r = (x + e.x) / 2;
p.l = (x + e.x + 1) / 2;
}
if(next(it) != loc1[e.d].end())
{
int x = next(it)->first;
ent1 &q = next(it)->second;
add_seg(q.lt, e.t - 1, x, q.l);
q.lt = e.t;
q.l = (x + e.x + 1) / 2;
p.r = (x + e.x) / 2;
}
}
else
{
e.d = -e.d;
auto it = loc1[e.d].find(e.x);
ent1 &p = it->second;
if(p.c > 1)
{
p.c--;
continue;
}
add_seg(p.lt, e.t, e.x, p.l);
add_seg(p.rt, e.t, e.x, p.r);
if(it != loc1[e.d].begin())
{
int x = prev(it)->first;
ent1 &q = prev(it)->second;
add_seg(q.rt, e.t, x, q.r);
q.rt = e.t + 1;
if(next(it) != loc1[e.d].end())
{
int y = next(it)->first;
q.r = (x + y) / 2;
}
else
q.r = INF;
}
if(next(it) != loc1[e.d].end())
{
int x = next(it)->first;
ent1 &q = next(it)->second;
add_seg(q.lt, e.t, x, q.l);
q.lt = e.t + 1;
if(it != loc1[e.d].begin())
{
int y = prev(it)->first;
q.l = (y + x + 1) / 2;
}
else
q.l = 1;
}
loc1[e.d].erase(it);
if(loc1[e.d].size() == 0)
{
if(cnt == k)
can.push_back({ cur, e.t });
cnt--;
}
}
}
sort(arr2.begin(), arr2.end());
int p = 0, sz = (int)can.size();
for(eve2 &e : arr2)
{
if(e.p == 1 || e.p == 3)
add(e);
else
{
while(p < sz && can[p].second < e.t)
p++;
if(p < sz && can[p].first <= e.t)
ans[e.y] = get(e.x);
else
ans[e.y] = -1;
}
}
for(int i = 0; i < q; i++)
printf("%d\n", ans[i]);
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:138:10: 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:142:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &x, &t, &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &l, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
63648 KB |
Output is correct |
| 2 |
Correct |
137 ms |
63712 KB |
Output is correct |
| 3 |
Correct |
58 ms |
63792 KB |
Output is correct |
| 4 |
Incorrect |
57 ms |
63792 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
63648 KB |
Output is correct |
| 2 |
Correct |
137 ms |
63712 KB |
Output is correct |
| 3 |
Correct |
58 ms |
63792 KB |
Output is correct |
| 4 |
Incorrect |
57 ms |
63792 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5023 ms |
294068 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5060 ms |
299472 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
63648 KB |
Output is correct |
| 2 |
Correct |
137 ms |
63712 KB |
Output is correct |
| 3 |
Correct |
58 ms |
63792 KB |
Output is correct |
| 4 |
Incorrect |
57 ms |
63792 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
63648 KB |
Output is correct |
| 2 |
Correct |
137 ms |
63712 KB |
Output is correct |
| 3 |
Correct |
58 ms |
63792 KB |
Output is correct |
| 4 |
Incorrect |
57 ms |
63792 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
