#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];
// segment: [t, t2] time, [x -> y] loc
// query : t time, t2 = -1, x loc, y idx
struct eve2
{
int t, t2, x, y;
bool operator <(const eve2 &e) const
{
return t != e.t ? t < e.t : t2 > e.t2;
}
};
vector<eve2> arr2;
list<pair<int, int>> mem2[MAXI + 10];
vector<eve2> naive;
void add(eve2 &e)
{
if(e.t <= e.t2 && e.x != e.y)
naive.push_back(e);
}
int get(int t, int x)
{
int r = 0;
for(eve2 &e : naive)
{
if(e.t <= t && t <= e.t2 && min(e.x, e.y) <= x && x <= max(e.x, e.y))
{
int c = abs(x - e.x);
r = max(r, c);
}
}
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, -1, l, i });
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;
arr2.push_back({ 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;
arr2.push_back({ 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;
}
arr2.push_back({ p.lt, e.t, e.x, p.l });
arr2.push_back({ p.rt, e.t, e.x, p.r });
if(it != loc1[e.d].begin())
{
int x = prev(it)->first;
ent1 &q = prev(it)->second;
arr2.push_back({ q.rt, e.t, x, q.r });
q.rt = e.t + 1;
if(next(it) != loc1[e.d].end())
q.r = (x + e.x) / 2;
else
q.r = INF;
}
if(next(it) != loc1[e.d].end())
{
int x = next(it)->first;
ent1 &q = next(it)->second;
arr2.push_back({ q.lt, e.t, x, q.l });
q.lt = e.t + 1;
if(it != loc1[e.d].begin())
q.l = (x + e.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.t2 != -1)
{
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.t, 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:92: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:96: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:103: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 |
37 ms |
39032 KB |
Output is correct |
| 2 |
Correct |
35 ms |
39140 KB |
Output is correct |
| 3 |
Correct |
40 ms |
39140 KB |
Output is correct |
| 4 |
Correct |
35 ms |
39368 KB |
Output is correct |
| 5 |
Incorrect |
43 ms |
39368 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
39032 KB |
Output is correct |
| 2 |
Correct |
35 ms |
39140 KB |
Output is correct |
| 3 |
Correct |
40 ms |
39140 KB |
Output is correct |
| 4 |
Correct |
35 ms |
39368 KB |
Output is correct |
| 5 |
Incorrect |
43 ms |
39368 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5038 ms |
100052 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5084 ms |
106764 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
39032 KB |
Output is correct |
| 2 |
Correct |
35 ms |
39140 KB |
Output is correct |
| 3 |
Correct |
40 ms |
39140 KB |
Output is correct |
| 4 |
Correct |
35 ms |
39368 KB |
Output is correct |
| 5 |
Incorrect |
43 ms |
39368 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
39032 KB |
Output is correct |
| 2 |
Correct |
35 ms |
39140 KB |
Output is correct |
| 3 |
Correct |
40 ms |
39140 KB |
Output is correct |
| 4 |
Correct |
35 ms |
39368 KB |
Output is correct |
| 5 |
Incorrect |
43 ms |
39368 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
