#include<bits/stdc++.h>
using namespace std;
int newN, N, K, Q, timeCount, xCount, x[300009], type[300009], a[300009], b[300009], location[300009], when[300009], ans[300009], realX[300009];
const int INF = 5e8;
int changesLine = 0;
vector < pair < int*, int > > changes[40];
pair < int, int > S[300009];
int prv[300009], nxt[300009];
vector < pair < int, int > > setChanges[40];
void update (int &x, int y)
{
if (y > x)
changes[changesLine].push_back ({&x, x}),
x = y;
}
void rollBack (int id)
{
reverse (changes[id].begin (), changes[id].end ());
for (auto it : changes[id])
*it.first = it.second;
changes[id].clear ();
}
const int maxSize = 300009;
int aib[2][maxSize];
void update (int lin, int pos, int val)
{
while (pos <= xCount)
update (aib[lin][pos], val),
pos += pos - (pos & (pos - 1));
}
int query (int lin, int pos)
{
int ans = -INF;
while (pos)
ans = max (ans, aib[lin][pos]),
pos &= pos - 1;
return ans;
}
int maxDist (int x)
{
int v1 = query (0, xCount - x + 1) + realX[x];
int v2 = query (1, x) - realX[x];
v1 = max (v1, v2);
if (v1 >= 1e8) return -1;
return v1;
}
void addSegm (int x0, int x2)
{
// printf ("+[%d, %d]\n", x0, x2);
int mid = (x0 + x2) / 2, pos;
if (mid < realX[1]) pos = 0;
else pos = lower_bound (realX + 1, realX + xCount + 1, mid + 1) - realX - 1;
if (pos >= 1) update (0, xCount - pos + 1, -x0);
if (pos < xCount) update (1, pos + 1, x2);
}
void delPoint (int it)
{
int it0 = prv[it], it2 = nxt[it];
int x0 = -INF, x2 = +INF;
if (type[it0] == type[it]) x0 = x[it0];
if (type[it2] == type[it]) x2 = x[it2];
if (x2 > x0)
addSegm (x0, x2);
changes[changesLine].push_back ({&nxt[it0], nxt[it0]});
changes[changesLine].push_back ({&prv[it2], prv[it2]});
nxt[it0] = it2, prv[it2] = it0;
}
pair < pair < int, int >, int > normS[300009];
void init ()
{
for (int i=1; i<=xCount; i++)
aib[0][i] = aib[1][i] = -INF;
for (int i=1; i<=N; i++)
if (a[i] <= b[i])
normS[++newN] = {{type[i], x[i]}, i};
sort (normS + 1, normS + newN + 1);
for (int i=1; i<=newN; i++)
S[i] = normS[i].first;
normS[newN + 1].second = newN + 1;
for (int i=1; i<=newN; i++)
prv[normS[i].second] = normS[i - 1].second,
nxt[normS[i].second] = normS[i + 1].second;
prv[newN + 1] = normS[newN].second, nxt[0] = normS[1].second;
S[0].second = -INF, S[newN + 1].second = +INF;
for (int i=1; i<=newN + 1; i++)
{
if (S[i].first == S[i - 1].first) addSegm (S[i - 1].second, S[i].second);
else
{
if (i > 1) addSegm (S[i - 1].second, +INF);
if (i <= newN) addSegm (-INF, S[i].second);
}
}
changes[changesLine].clear ();
/* printf ("%d\n", maxDist (1));
printf ("%d\n", maxDist (2));
exit (0);*/
// printf ("done initializing\n");
}
int mpX[300009];
vector < int > normT;
void normalize ()
{
sort (normT.begin (), normT.end ());
normT.erase (unique (normT.begin (), normT.end ()), normT.end ());
timeCount = normT.size ();
sort (mpX + 1, mpX + Q + 1);
for (int i=1; i<=Q; i++)
if (i == 1 || mpX[i] != mpX[i - 1])
realX[++xCount] = mpX[i];
for (int i=1; i<=Q; i++)
when[i] = lower_bound (normT.begin (), normT.end (), when[i]) - normT.begin () + 1,
location[i] = lower_bound (realX + 1, realX + xCount, location[i]) - realX;
for (int i=1; i<=N; i++)
{
a[i] = lower_bound (normT.begin (), normT.end (), a[i]) - normT.begin () + 1;
if (b[i] < normT[0]) b[i] = 0;
else b[i] = lower_bound (normT.begin (), normT.end (), b[i] + 1) - normT.begin ();
}
}
vector < int > delList[1200009], qry[300009];
void addToDelList (int nod, int st, int dr, int x, int y, int val)
{
if (x <= st && dr <= y)
{
delList[nod].push_back (val);
return ;
}
int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
if (x <= mij) addToDelList (f1, st, mij, x, y, val);
if (mij < y) addToDelList (f2, mij + 1, dr, x, y, val);
}
void buildDelList ()
{
for (int i=1; i<=N; i++)
if (a[i] <= b[i])
{
if (a[i] > 1)
addToDelList (1, 1, timeCount, 1, a[i] - 1, i);
if (b[i] < timeCount)
addToDelList (1, 1, timeCount, b[i] + 1, timeCount, i);
}
}
void solveDC (int nod, int st, int dr)
{
changesLine ++;
for (auto it : delList[nod])
delPoint (it);
if (st == dr)
{
/*printf ("%d:", st);
for (int i=nxt[0]; i<=newN; i=nxt[i])
printf (" %d", i);
printf ("\n");*/
for (auto it : qry[st])
ans[it] = maxDist (location[it]);
}
else
{
int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
solveDC (f1, st, mij);
solveDC (f2, mij + 1, dr);
}
rollBack (changesLine), changesLine --;
//for (auto it : delList[nod])
// printf ("roll back\n");
}
void Read (int &x);
int main ()
{
//freopen ("100", "r", stdin);
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
Read (N), Read (K), Read (Q), normT.resize (Q);
for (int i=1; i<=N; i++)
Read (x[i]), Read (type[i]), Read (a[i]), Read (b[i]);
for (int i=1; i<=Q; i++)
Read (location[i]), Read (when[i]),
normT[i - 1] = when[i], mpX[i] = location[i];
normalize ();
init ();
buildDelList ();
for (int i=1; i<=Q; i++)
qry[when[i]].push_back (i);
solveDC (1, 1, timeCount);
for (int i=1; i<=Q; i++)
printf ("%d\n", ans[i]);
return 0;
}
const int maxl = 500000;
int pos = maxl - 1;
char buff[maxl];
void Next ()
{
if (++pos == maxl)
fread (buff, 1, maxl, stdin), pos = 0;
}
void Read (int &x)
{
while (buff[pos] < '0' || buff[pos] > '9') Next ();
for (x = 0; buff[pos] >= '0' && buff[pos] <= '9'; Next ()) x = x * 10 + buff[pos] - '0';
}
Compilation message
new_home.cpp: In function 'void Next()':
new_home.cpp:215:37: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread (buff, 1, maxl, stdin), pos = 0;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
35576 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
35684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
35576 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
35684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
615 ms |
81036 KB |
Output is correct |
| 2 |
Correct |
640 ms |
84276 KB |
Output is correct |
| 3 |
Correct |
567 ms |
84276 KB |
Output is correct |
| 4 |
Correct |
696 ms |
84276 KB |
Output is correct |
| 5 |
Correct |
771 ms |
123276 KB |
Output is correct |
| 6 |
Correct |
635 ms |
123276 KB |
Output is correct |
| 7 |
Correct |
510 ms |
123276 KB |
Output is correct |
| 8 |
Correct |
634 ms |
123276 KB |
Output is correct |
| 9 |
Correct |
654 ms |
123276 KB |
Output is correct |
| 10 |
Correct |
710 ms |
123276 KB |
Output is correct |
| 11 |
Correct |
388 ms |
123276 KB |
Output is correct |
| 12 |
Correct |
524 ms |
123276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2412 ms |
139924 KB |
Output is correct |
| 2 |
Correct |
260 ms |
139924 KB |
Output is correct |
| 3 |
Correct |
2900 ms |
143988 KB |
Output is correct |
| 4 |
Incorrect |
1601 ms |
143988 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
35576 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
35684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
35576 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
35684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
