// M
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 300005, MXN = N * 3, INF = 1e9 + 9;
struct Data {int l, r, a, b;};
int n, q, k, nwtp, nwtm, X[N], T[N], L[N], R[N], Y[N], Z[N], RS[N];
map < pair < int , int > , vector < tuple < int , int , int > > > MP[N];
vector < pair < int , int > > E;
multiset < int > ST[N];
vector < Data > QD[MXN * 4];
vector < int > U, OP, V[N * 2][2];
inline int GetId(int val)
{
return (int)(lower_bound(U.begin(), U.end(), val) - U.begin());
}
inline void Adder(int l, int r, int a, int b)
{
//printf("Adding %d %d :: %d %d ::: %d %d\n", l, r, a, b, nwtp, nwtm);
MP[nwtp][make_pair(l, r)].push_back(make_tuple(nwtm, a, b));
}
inline void Deler(int l, int r, int a, int b)
{
//printf("Deleting %d %d :: %d %d ::: %d %d\n", l, r, a, b, nwtp, nwtm);
MP[nwtp][make_pair(l, r)].push_back(make_tuple(nwtm, a, b));
}
inline void Do(int l, int r)
{
int mid = (l + r + 1) >> 1;
// [l, mid)
Adder(l, mid, 1, -l);
// [mid, r]
Adder(mid, r + 1, 0, r);
}
inline void Undo(int l, int r)
{
int mid = (l + r + 1) >> 1;
// [l, mid)
Deler(l, mid, 1, -l);
// [mid, r]
Deler(mid, r + 1, 0, r);
}
inline void Add(int tp, int x)
{
auto it = ST[tp].lower_bound(x);
assert(it != ST[tp].end());
if (* it == x)
return void(ST[tp].insert(x));
int r = * it; it --;
int l = * it;
Undo(l, r);
Do(l, x);
Do(x, r);
ST[tp].insert(x);
}
inline void Del(int tp, int x)
{
auto it = ST[tp].lower_bound(x);
assert(* it == x);
it = ST[tp].erase(it);
if (* it == x)
return ;
int r = * it; it --;
int l = * it;
Undo(l, x);
Undo(x, r);
Do(l, r);
}
void AddSeg(int l, int r, int a, int b)
{
l += (int)U.size();
r += (int)U.size();
for (; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
{
if (!V[l][a].size() || V[l][a].back() < b)
V[l][a].push_back(b), OP.push_back(l << 1 ^ a);
l ++;
}
if (r & 1)
{
r --;
if (!V[r][a].size() || V[r][a].back() < b)
V[r][a].push_back(b), OP.push_back(r << 1 ^ a);
}
}
}
pair < int , int > GetSeg(int i)
{
pair < int , int > rt = {-INF, -INF};
for (i += (int)U.size(); i; i >>= 1)
{
if (V[i][0].size())
rt.first = max(rt.first, V[i][0].back());
if (V[i][1].size())
rt.second = max(rt.second, V[i][1].back());
}
return rt;
}
void AddQuery(int le, int ri, Data d, int id = 1, int l = 0, int r = (int)E.size())
{
if (ri <= l || r <= le)
return ;
if (le <= l && r <= ri)
return void(QD[id].push_back(d));
AddQuery(le, ri, d, lc, l, md);
AddQuery(le, ri, d, rc, md, r);
}
void DFS(int id = 1, int l = 0, int r = (int)E.size())
{
OP.push_back(-1);
for (Data &d : QD[id])
AddSeg(d.l, d.r, d.a, d.b);//, printf("Adding %d , %d :: %d , %d\n", d.l, d.r, d.a, d.b);
if (r - l < 2 && E[l].second > 0)
{
int i = E[l].second;
int y = GetId(Y[i]);
pair < int , int> rt = GetSeg(y);
RS[i] = max(rt.first - Y[i], rt.second + Y[i]);
//printf("%d :: %d\n", rt.first, rt.second);
if (RS[i] > (int)1e8)
RS[i] = -1;
//printf("Answering ...\n");
}
if (r - l > 1)
DFS(lc, l, md), DFS(rc, md, r);
while (OP.size() && OP.back() != -1)
{
// Undo
int uid = OP.back() >> 1, ua = OP.back() & 1;
V[uid][ua].pop_back();
//printf("Deleteing.\n");
OP.pop_back();
}
OP.pop_back();
}
int main()
{
scanf("%d%d%d", &n, &k, &q);
for (int i = 1; i <= n; i ++)
{
scanf("%d%d%d%d", &X[i], &T[i], &L[i], &R[i]);
E.push_back({L[i], -i});
E.push_back({R[i] + 1, -i});
}
for (int i = 1; i <= q; i ++)
{
scanf("%d%d", &Y[i], &Z[i]);
E.push_back({Z[i], i});
U.push_back(Y[i]);
}
sort(E.begin(), E.end());
sort(U.begin(), U.end());
U.resize(unique(U.begin(), U.end()) - U.begin());
nwtm = -1;
for (int i = 1; i <= k; i ++)
{
nwtp = i;
ST[i].insert(-INF);
ST[i].insert(INF);
Do(-INF, INF);
}
for (auto e : E)
{
nwtm ++;
int i = e.second;
if (i < 0)
{
i = -i;
nwtp = T[i];
if (e.first == L[i])
Add(T[i], X[i]);
else
Del(T[i], X[i]);
continue;
}
}
nwtm ++;
for (int i = 1; i <= k; i ++)
{
ST[i].clear();
for (auto a : MP[i])
{
int l = a.first.first;
int r = a.first.second;
l = GetId(l);
r = GetId(r);
if (l == r)
continue;
vector < tuple < int , int , int > > &vec = a.second;
if (vec.size() & 1)
vec.push_back(make_tuple(nwtm, -1, -1));
/*printf("=====================\n");
printf("%d == %d\n", l, r);
for (auto e : vec)
{
int t, y, z;
tie(t, y, z) = e;
printf("%d :: %d :: %d\n", t, y, z);
}*/
for (int j = 0; j < (int)vec.size(); j += 2)
{
int t1, t2, y, z;
tie(t2, y, z) = vec[j + 1];
tie(t1, y, z) = vec[j];
if (t1 == t2 || t2 <= 0)
continue;
//printf("Time [%d, %d] : %d , %d , %d , %d\n", t1, t2, l, r, y, z);
AddQuery(t1, t2, Data {l, r, y, z});
}
}
}
DFS();
for (int i = 1; i <= q; i ++)
printf("%d\n", RS[i]);
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
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", &n, &k, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:145:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &X[i], &T[i], &L[i], &R[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:151:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &Y[i], &Z[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
141304 KB |
Output is correct |
| 2 |
Correct |
80 ms |
141432 KB |
Output is correct |
| 3 |
Correct |
87 ms |
141304 KB |
Output is correct |
| 4 |
Correct |
85 ms |
141308 KB |
Output is correct |
| 5 |
Incorrect |
80 ms |
141432 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
141304 KB |
Output is correct |
| 2 |
Correct |
80 ms |
141432 KB |
Output is correct |
| 3 |
Correct |
87 ms |
141304 KB |
Output is correct |
| 4 |
Correct |
85 ms |
141308 KB |
Output is correct |
| 5 |
Incorrect |
80 ms |
141432 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5087 ms |
854540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5079 ms |
782616 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
141304 KB |
Output is correct |
| 2 |
Correct |
80 ms |
141432 KB |
Output is correct |
| 3 |
Correct |
87 ms |
141304 KB |
Output is correct |
| 4 |
Correct |
85 ms |
141308 KB |
Output is correct |
| 5 |
Incorrect |
80 ms |
141432 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
141304 KB |
Output is correct |
| 2 |
Correct |
80 ms |
141432 KB |
Output is correct |
| 3 |
Correct |
87 ms |
141304 KB |
Output is correct |
| 4 |
Correct |
85 ms |
141308 KB |
Output is correct |
| 5 |
Incorrect |
80 ms |
141432 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
