#include<bits/stdc++.h>
using namespace std;
int N, K, Q, timeCount, xCount, x[300009], type[300009], a[300009], b[300009], location[300009], when[300009], ans[300009], realX[600009];
const int INF = 5e8;
int changesLine = 0;
vector < pair < int*, int > > changes[20];
vector < multiset < int > > S;
vector < pair < int, int > > setChanges[20];
void update (int &x, int y)
{
if (y > x)
changes[changesLine].push_back ({&x, x}),
x = y;
}
int emptySets = 0;
void rollBack (int id)
{
reverse (changes[id].begin (), changes[id].end ());
for (auto it : changes[id])
*it.first = it.second;
changes[id].clear ();
for (auto it : setChanges[id])
emptySets -= S[it.first].empty (),
S[it.first].insert (it.second);
setChanges[id].clear ();
}
const int maxSize = 1200009;
int aint[2][maxSize];
void update (int lin, int nod, int st, int dr, int x, int y, int lazyVal)
{
if (x <= st && dr <= y)
{
if (lin == 0) update (aint[lin][nod], lazyVal + realX[st] - realX[x]);
else update (aint[lin][nod], lazyVal - (realX[st] - realX[x]));
return ;
}
int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
update (aint[lin][f1], aint[lin][nod]);
if (lin == 0) update (aint[lin][f2], aint[lin][nod] + realX[mij + 1] - realX[st]);
else update (aint[lin][f2], aint[lin][nod] - (realX[mij + 1] - realX[st]));
if (x <= mij) update (lin, f1, st, mij, x, y, lazyVal);
if (mij < y) update (lin, f2, mij + 1, dr, x, y, lazyVal);
}
int query (int lin, int nod, int st, int dr, int pos)
{
if (st == dr) return aint[lin][nod];
int mij = (st + dr) >> 1, ans = aint[lin][nod], curr;
if (lin == 0) ans += realX[pos] - realX[st];
else ans -= (realX[pos] - realX[st]);
if (pos <= mij) curr = query (lin, nod << 1, st, mij, pos);
else curr = query (lin, nod << 1 | 1, mij + 1, dr, pos);
return max (ans, curr);
}
int firstBigger (int val)
{
int p = 1, u = xCount, mij, ras = xCount + 1;
while (p <= u)
{
mij = (p + u) >> 1;
if (realX[mij] > val) ras = mij, u = mij - 1;
else p = mij + 1;
}
return ras;
}
int lastSmaller (int val)
{
int p = 1, u = xCount, mij, ras = 0;
while (p <= u)
{
mij = (p + u) >> 1;
if (realX[mij] < val) ras = mij, p = mij + 1;
else u = mij - 1;
}
return ras;
}
int maxDist (int x)
{
int i = lastSmaller (x + 1), j = i + 1;
int v1, v2;
if (realX[i] == x)
v1 = query (0, 1, 1, xCount, i),
v2 = query (1, 1, 1, xCount, i);
else
{
if (i != 0) v1 = query (0, 1, 1, xCount, i) + x - realX[i];
else v1 = -INF;
if (j <= xCount) v2 = query (1, 1, 1, xCount, j) + realX[j] - x;
else v2 = -INF;
}
return max (v1, v2);
}
void addLine (int type, int bg, int nd)
{
int x = firstBigger (bg - 1), y = lastSmaller (nd + 1);
if (x <= y)
{
if (type == 0) update (0, 1, 1, xCount, x, y, realX[x] - bg);
else update (1, 1, 1, xCount, x, y, nd - realX[x]);
}
}
void addSegm (int x0, int x2)
{
int mid = (x0 + x2) / 2;
addLine (0, x0, mid);
addLine (1, mid + 1, x2);
}
void delPoint (int type, int x)
{
//printf ("del (%d, %d)\n", type, x);
auto it = S[type].lower_bound (x), it0 = it, it2 = it;
int x0, x2;
if (it0 == S[type].begin ()) x0 = -INF;
else it0 --, x0 = *it0;
it2 ++;
if (it2 == S[type].end ()) x2 = +INF;
else x2 = *it2;
if (x0 != x && x2 != x)
addSegm (x0, x2);
setChanges[changesLine].push_back ({type, x});
S[type].erase (it), emptySets += S[type].empty ();
}
void init ()
{
for (int i=1; i<=4 * xCount; i++)
aint[0][i] = aint[1][i] = -INF;
for (int i=1; i<=K; i++)
{
emptySets += S[i].empty ();
int lastX = -INF;
for (auto it : S[i])
addSegm (lastX, it),
lastX = it;
addSegm (lastX, +INF);
}
changes[changesLine].clear ();
}
map < int, int > normT, mpX;
void normalize ()
{
for (auto &it : normT)
it.second = ++timeCount;
for (auto &it : mpX)
it.second = ++xCount, realX[xCount] = it.first;
for (int i=1; i<=Q; i++)
when[i] = normT[when[i]];
for (int i=1; i<=N; i++)
a[i] = normT[a[i]], b[i] = normT[b[i]];
}
vector < vector < int > > delList, qry;
void addToDelList (int nod, int st, int dr, int x, int y, int val)
{
if (x <= st && dr <= y)
{
//printf ("add %d to delList[%d]\n", val, nod);
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 ()
{
delList.resize (4 * (timeCount + 1));
for (int i=1; i<=N; 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 (type[it], x[it]);
if (st == dr)
{
for (auto it : qry[st])
if (emptySets > 0) ans[it] = -1;
else 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 --;
}
void Read (int &x);
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
Read (N), Read (K), Read (Q), S.resize (K + 1);
for (int i=1; i<=N; i++)
Read (x[i]), Read (type[i]), Read (a[i]), Read (b[i]),
normT[a[i]] = 1, normT[b[i]] = 1, mpX[x[i]] = 1, S[type[i]].insert (x[i]);
for (int i=1; i<=Q; i++)
Read (location[i]), Read (when[i]), normT[when[i]] = 1;
normalize ();
init ();
buildDelList ();
qry.resize (timeCount + 1);
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:243: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 |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
612 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
612 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
612 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
612 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2299 ms |
308468 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4158 ms |
446476 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
612 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
612 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
612 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
612 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
