//#pragma GCC optimize ("O3")
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <map>
#include <iterator>
using namespace std;
#define INF 100000000
static char buf[33554432];
static int fio_idx = 0;
static inline int _readInt() {
int x = 0;
int c = buf[fio_idx++];
if(c <= 32) c = buf[fio_idx++];
while(c > 32) x = 10 * x + (c - '0'), c = buf[fio_idx++];
return x;
}
int n, k, q, bp;
int com[524288];
int c_sz;
inline int idx(int x)
{
return lower_bound(com, com + c_sz, x) - com;
}
struct eve
{
int t, x, d;
bool operator <(const eve &e) const
{
return t != e.t ? t < e.t : d > e.d;
}
};
struct pos
{
int c, l, lt, r, rt;
};
eve arr[1048576];
map<int, pos> loc[524288];
struct seg
{
int t1, t2, x, y;
bool operator <(const seg &e) const
{
return x < e.x;
}
};
seg sor0[1048576];
seg sor1[1048576];
int s_sz0, s_sz1;
inline void add_seg(const int &t1, const int &t2, const int &x, const int &y)
{
if(t1 > t2 || x == y)
return;
int nt1 = bp + idx(t1);
int nt2 = bp + idx(t2 + 1) - 1;
if(nt1 > nt2)
return;
if(y < x)
sor0[s_sz0++] = { nt1, nt2, y, x };
else
sor1[s_sz1++] = { nt1, nt2, -y, -x };
}
struct ent
{
// v0 : dec, v1 : inc, q : query
// v : { x, y }
// q : { x, i }
vector<pair<int, int>> v0, v1;
vector<pair<int, int>> q;
};
ent mem[1048576];
struct que
{
int l, y, i;
bool operator <(const que &x) const
{
return l < x.l;
}
};
que inp[524288];
bool chk[524288];
int ans[524288];
int main()
{
fread(buf, sizeof(buf[0]), sizeof(buf), stdin);
n = _readInt();
k = _readInt();
q = _readInt();
for(int i = 0; i < n; i++)
{
int x, t, a, b;
x = _readInt();
t = _readInt();
a = _readInt();
b = _readInt();
arr[2 * i] = { a, x, t };
arr[2 * i + 1] = { b, x, -t };
}
for(int i = 0; i < q; i++)
{
int l, y;
l = _readInt();
y = _readInt();
inp[i] = { l, y, i };
com[i] = y;
}
sort(com, com + q);
c_sz = unique(com, com + q) - com;
for(bp = 1; bp < c_sz; bp *= 2);
sort(arr, arr + 2 * n);
int cur, cnt = 0;
for(int u = 0; u < 2 * n; u++)
{
eve &e = arr[u];
if(e.d > 0)
{
if(loc[e.d].empty())
{
cnt++;
if(cnt == k)
cur = e.t;
}
auto it = loc[e.d].find(e.x);
if(it != loc[e.d].end())
{
it->second.c++;
continue;
}
it = loc[e.d].insert({ e.x,{ 1, 1, e.t, INF, e.t } }).first;
pos &p = it->second;
if(it != loc[e.d].begin())
{
it--;
int x = it->first;
pos &q = 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;
}
it++;
if(it != loc[e.d].end())
{
int x = it->first;
pos &q = 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 = loc[e.d].find(e.x);
pos &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);
auto it2 = prev(it);
auto it3 = next(it);
if(it != loc[e.d].begin())
{
int x = it2->first;
pos &q = it2->second;
add_seg(q.rt, e.t, x, q.r);
q.rt = e.t + 1;
if(it3 != loc[e.d].end())
{
int y = it3->first;
q.r = (x + y) / 2;
}
else
q.r = INF;
}
if(it3 != loc[e.d].end())
{
int x = it3->first;
pos &q = it3->second;
add_seg(q.lt, e.t, x, q.l);
q.lt = e.t + 1;
if(it != loc[e.d].begin())
{
int y = it2->first;
q.l = (y + x + 1) / 2;
}
else
q.l = 1;
}
loc[e.d].erase(it);
if(loc[e.d].empty())
{
if(cnt == k)
{
int t1 = idx(cur);
int t2 = idx(e.t + 1) - 1;
for(int i = t1; i <= t2; i++)
chk[i] = 1;
}
cnt--;
}
}
}
sort(inp, inp + q);
for(int u = 0; u < q; u++)
{
que &e = inp[u];
e.y = idx(e.y);
if(chk[e.y])
{
e.y += bp;
while(e.y)
{
mem[e.y].q.push_back({ e.l, e.i });
e.y /= 2;
}
}
else
ans[e.i] = -1;
}
{
sort(sor0, sor0 + s_sz0);
for(int u = 0; u < s_sz0; u++)
{
seg &e = sor0[u];
while(e.t1 < e.t2)
{
if(e.t1 % 2 == 1)
{
mem[e.t1].v0.push_back({ e.x, e.y });
e.t1++;
}
if(e.t2 % 2 == 0)
{
mem[e.t2].v0.push_back({ e.x, e.y });
e.t2--;
}
e.t1 /= 2;
e.t2 /= 2;
}
if(e.t1 == e.t2)
mem[e.t1].v0.push_back({ e.x, e.y });
}
}
{
sort(sor1, sor1 + s_sz1);
for(int u = 0; u < s_sz1; u++)
{
seg &e = sor1[u];
while(e.t1 < e.t2)
{
if(e.t1 % 2 == 1)
{
mem[e.t1].v1.push_back({ e.x, e.y });
e.t1++;
}
if(e.t2 % 2 == 0)
{
mem[e.t2].v1.push_back({ e.x, e.y });
e.t2--;
}
e.t1 /= 2;
e.t2 /= 2;
}
if(e.t1 == e.t2)
mem[e.t1].v1.push_back({ e.x, e.y });
}
}
for(int x = 1; x <= bp + c_sz - 1; x++)
{
if(mem[x].q.empty())
continue;
int mx, p1, p2;
if(!mem[x].v0.empty())
{
mx = p1 = p2 = 0;
while(p2 < mem[x].q.size())
{
if(p1 != mem[x].v0.size() && mem[x].v0[p1].first <= mem[x].q[p2].first)
{
mx = max(mx, mem[x].v0[p1].second);
p1++;
}
else
{
ans[mem[x].q[p2].second] = max(ans[mem[x].q[p2].second], mx - mem[x].q[p2].first);
p2++;
}
}
}
if(!mem[x].v1.empty())
{
mx = -INF;
p1 = 0;
p2 = mem[x].q.size() - 1;
while(p2 >= 0)
{
if(p1 != mem[x].v1.size() && mem[x].v1[p1].first <= -mem[x].q[p2].first)
{
mx = max(mx, mem[x].v1[p1].second);
p1++;
}
else
{
ans[mem[x].q[p2].second] = max(ans[mem[x].q[p2].second], mx + mem[x].q[p2].first);
p2--;
}
}
}
}
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:324:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p2 < mem[x].q.size())
~~~^~~~~~~~~~~~~~~~~
new_home.cpp:326:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(p1 != mem[x].v0.size() && mem[x].v0[p1].first <= mem[x].q[p2].first)
~~~^~~~~~~~~~~~~~~~~~~
new_home.cpp:345:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(p1 != mem[x].v1.size() && mem[x].v1[p1].first <= -mem[x].q[p2].first)
~~~^~~~~~~~~~~~~~~~~~~
new_home.cpp:104:10: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread(buf, sizeof(buf[0]), sizeof(buf), stdin);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
98808 KB |
Output is correct |
| 2 |
Correct |
79 ms |
98928 KB |
Output is correct |
| 3 |
Correct |
79 ms |
98976 KB |
Output is correct |
| 4 |
Incorrect |
80 ms |
99152 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
98808 KB |
Output is correct |
| 2 |
Correct |
79 ms |
98928 KB |
Output is correct |
| 3 |
Correct |
79 ms |
98976 KB |
Output is correct |
| 4 |
Incorrect |
80 ms |
99152 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1461 ms |
229644 KB |
Output is correct |
| 2 |
Incorrect |
1545 ms |
229644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3367 ms |
305212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
98808 KB |
Output is correct |
| 2 |
Correct |
79 ms |
98928 KB |
Output is correct |
| 3 |
Correct |
79 ms |
98976 KB |
Output is correct |
| 4 |
Incorrect |
80 ms |
99152 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
98808 KB |
Output is correct |
| 2 |
Correct |
79 ms |
98928 KB |
Output is correct |
| 3 |
Correct |
79 ms |
98976 KB |
Output is correct |
| 4 |
Incorrect |
80 ms |
99152 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
