#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 (int)(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;
};
vector<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;
}
};
vector<seg> sor[2];
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 }
vector<pair<int, int>> v[2];
vector<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);
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);
arr.push_back({ a, x, t });
arr.push_back({ b, x, -t });
}
for(int i = 0; i < q; i++)
{
int l, y;
scanf("%d%d", &l, &y);
inp.push_back({ l, y, i });
com.push_back(y);
}
sort(inp.begin(), inp.end());
sort(com.begin(), com.end());
com.erase(unique(com.begin(), com.end()), com.end());
int sz = (int)com.size();
for(bp = 1; bp < sz; bp *= 2);
sort(arr.begin(), arr.end());
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--;
}
}
}
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++)
{
sort(sor[i].begin(), sor[i].end());
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++)
{
for(int i = 0; i < 2; i++)
{
int mx, p1, p2, sz1, sz2;
mx = p1 = p2 = 0;
sz1 = (int)mem[x].v[i].size();
sz2 = (int)mem[x].q.size();
while(p2 < sz2)
{
int qx, qi;
tie(qx, qi) = mem[x].q[p2];
if(i == 1)
qx = INF - qx + 1;
if(p1 != sz1 && mem[x].v[i][p1].first <= qx)
{
mx = max(mx, mem[x].v[i][p1].second);
p1++;
}
else
{
ans[qi] = max(ans[qi], max(0, mx - qx));
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:104: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:108: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:116: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 |
76 ms |
88184 KB |
Output is correct |
| 2 |
Correct |
79 ms |
88280 KB |
Output is correct |
| 3 |
Correct |
77 ms |
88280 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
88464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
88184 KB |
Output is correct |
| 2 |
Correct |
79 ms |
88280 KB |
Output is correct |
| 3 |
Correct |
77 ms |
88280 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
88464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2101 ms |
241480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4638 ms |
324208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
88184 KB |
Output is correct |
| 2 |
Correct |
79 ms |
88280 KB |
Output is correct |
| 3 |
Correct |
77 ms |
88280 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
88464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
88184 KB |
Output is correct |
| 2 |
Correct |
79 ms |
88280 KB |
Output is correct |
| 3 |
Correct |
77 ms |
88280 KB |
Output is correct |
| 4 |
Incorrect |
75 ms |
88464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
