#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;
static char buf[17100100]; // size : any number geq than 1024
static int fio_idx = 0;
static int bytes = 0;
static inline int _read() {
if(!bytes || fio_idx == bytes) {
bytes = (int)fread(buf, sizeof(buf[0]), sizeof(buf), stdin);
fio_idx = 0;
}
return buf[fio_idx++];
}
static inline int _readInt() {
int x = 0;
int c = _read();
while(c <= 32) c = _read();
while(c > 32) x = 10 * x + (c - '0'), c = _read();
return x;
}
int n, k, q, bp;
vector<int> com;
inline int idx(int x)
{
return lower_bound(com.begin(), com.end(), x) - com.begin();
}
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;
};
list<eve> arr;
map<int, pos> loc[MAXN + 10];
struct seg
{
int t1, t2, x, y;
bool operator <(const seg &e) const
{
return x < e.x;
}
};
list<seg> sor[2];
inline void add_seg(int t1, int t2, int x, 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)
sor[0].push_back({ nt1, nt2, y, x });
else
sor[1].push_back({ nt1, nt2, INF - y + 1, INF - x + 1 });
}
struct ent
{
// v0 : dec, v1 : inc, q : query
// v : { x, y }
// q : { x, i }
list<pair<int, int>> v[2];
list<pair<int, int>> q;
};
ent mem[MAXI + 10];
struct que
{
int l, y, i;
bool operator <(const que &x) const
{
return l < x.l;
}
};
vector<que> inp;
bool chk[MAXN + 10];
int ans[MAXN + 10];
int main()
{
//freopen("in", "r", stdin);
//freopen("out", "w", stdout);
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.push_back({ a, x, t });
arr.push_back({ b, x, -t });
}
for(int i = 0; i < q; i++)
{
int l, y;
l = _readInt();
y = _readInt();
inp.push_back({ l, y, i });
com.push_back(y);
}
sort(com.begin(), com.end());
com.erase(unique(com.begin(), com.end()), com.end());
int sz = com.size();
for(bp = 1; bp < sz; bp *= 2);
arr.sort();
int cur, cnt = 0;
for(eve &e : arr)
{
if(e.d > 0)
{
if(loc[e.d].size() == 0)
{
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())
{
int x = prev(it)->first;
pos &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) != loc[e.d].end())
{
int x = next(it)->first;
pos &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 = 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);
if(it != loc[e.d].begin())
{
int x = prev(it)->first;
pos &q = prev(it)->second;
add_seg(q.rt, e.t, x, q.r);
q.rt = e.t + 1;
if(next(it) != loc[e.d].end())
{
int y = next(it)->first;
q.r = (x + y) / 2;
}
else
q.r = INF;
}
if(next(it) != loc[e.d].end())
{
int x = next(it)->first;
pos &q = next(it)->second;
add_seg(q.lt, e.t, x, q.l);
q.lt = e.t + 1;
if(it != loc[e.d].begin())
{
int y = prev(it)->first;
q.l = (y + x + 1) / 2;
}
else
q.l = 1;
}
loc[e.d].erase(it);
if(loc[e.d].size() == 0)
{
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.begin(), inp.end());
for(que &e : inp)
{
int x = idx(e.y);
if(chk[x])
{
x += bp;
while(x)
{
mem[x].q.push_back({ e.l, e.i });
x /= 2;
}
}
else
ans[e.i] = -1;
}
for(int i = 0; i < 2; i++)
{
sor[i].sort();
for(seg &e : sor[i])
{
int t1 = e.t1;
int t2 = e.t2;
while(t1 < t2)
{
if(t1 % 2 == 1)
{
mem[t1].v[i].push_back({ e.x, e.y });
t1++;
}
if(t2 % 2 == 0)
{
mem[t2].v[i].push_back({ e.x, e.y });
t2--;
}
t1 /= 2;
t2 /= 2;
}
if(t1 == t2)
mem[t1].v[i].push_back({ e.x, e.y });
}
}
for(int x = 1; x <= bp + sz - 1; x++)
{
{
int mx = 0;
auto it1 = mem[x].v[0].begin();
auto it2 = mem[x].q.begin();
while(it2 != mem[x].q.end())
{
if(it1 != mem[x].v[0].end() && it1->first <= it2->first)
{
mx = max(mx, it1->second);
it1++;
}
else
{
ans[it2->second] = max(ans[it2->second], mx - it2->first);
it2++;
}
}
}
{
int mx = 0;
auto it1 = mem[x].v[0].begin();
auto it2 = mem[x].q.rbegin();
while(it2 != mem[x].q.rend())
{
int qx = INF - it2->first + 1;
if(it1 != mem[x].v[0].end() && it1->first <= qx)
{
mx = max(mx, it1->second);
it1++;
}
else
{
ans[it2->second] = max(ans[it2->second], mx - qx);
it2++;
}
}
}
}
for(int i = 0; i < q; i++)
printf("%d\n", ans[i]);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
88312 KB |
Output is correct |
| 2 |
Correct |
72 ms |
88488 KB |
Output is correct |
| 3 |
Correct |
72 ms |
88488 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
88488 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
88312 KB |
Output is correct |
| 2 |
Correct |
72 ms |
88488 KB |
Output is correct |
| 3 |
Correct |
72 ms |
88488 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
88488 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5038 ms |
486728 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5052 ms |
709984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
88312 KB |
Output is correct |
| 2 |
Correct |
72 ms |
88488 KB |
Output is correct |
| 3 |
Correct |
72 ms |
88488 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
88488 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
88312 KB |
Output is correct |
| 2 |
Correct |
72 ms |
88488 KB |
Output is correct |
| 3 |
Correct |
72 ms |
88488 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
88488 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
