// M
#include<bits/stdc++.h>
using namespace std;
mt19937 Rnd(time(0));
struct Node
{
int a[2] = {0, 0}, lz[2] = {-1, -1}, id = -1, p = 0;
Node * l = NULL, * r = NULL;
};
inline bool Less(int * a, int x, int w)
{
if (w == -1)
return a[0] < x;
if (w == -2)
return a[1] > x;
return (a[0] < x || (a[0] == x && a[1] > w));
}
inline void Upd(Node * T, int * val)
{
if (!T)
return ;
for (int w = 0; w < 2; w ++)
T->a[w] = max(T->a[w], val[w]), T->lz[w] = max(T->lz[w], val[w]);
}
inline void Shift(Node * T)
{
if (!T)
return ;
Upd(T->l, T->lz);
Upd(T->r, T->lz);
T->lz[0] = T->lz[1] = -1;
}
void Split(Node * T, Node * &L, Node * &R, int x, int w)
{
if (!T)
return void(L = R = NULL);
Shift(T);
if (Less(T->a, x, w))
Split(T->r, T->r, R, x, w), L = T;
else
Split(T->l, L, T->l, x, w), R = T;
}
void Merge(Node * &T, Node * L, Node * R)
{
Shift(L); Shift(R);
if (!L) T = R;
else if (!R) T = L;
else if (L->p > R->p) Merge(L->r, L->r, R), T = L;
else Merge(R->l, L, R->l), T = R;
}
const int N = 1500006, MXN = 3e6 + 109;
int n, m, q, tscnt, A[N], B[N], TP[N], L[N], nL[N], ST[N], rev[N];
int Last[MXN], MN[MXN * 2];
int Sub2 = 1, Sub4 = 0;
vector < int > U, V[(int)(1e6 + 100)];
pair < int , int > Res[N];
inline int GetMin(int l, int r)
{
int rt = q + 1;
l += MXN; r += MXN;
for (; l < r; l >>= 1, r >>= 1)
{
if (l & 1) rt = min(rt, MN[l ++]);
if (r & 1) rt = min(rt, MN[-- r]);
}
return rt;
}
inline void Add(Node * &T, int mxy, int mxx, int * a)
{
if (!T)
return ;
Node * X = NULL, * Y = NULL, * Z = NULL;
Split(T, X, Y, mxy, -2);
Split(Y, Y, Z, mxx + 1, -1);
Upd(Y, a);
Merge(T, X, Y);
Merge(T, T, Z);
return ;
}
inline void Insert(Node * &T, int a, int b, int id)
{
Node * X = NULL, * Y = NULL, * Z = new Node;
Split(T, X, Y, a, b);
Z->a[0] = a;
Z->a[1] = b;
Z->lz[0] = Z->lz[1] = 0;
Z->p = id;//Rnd();
Z->id = id;
Merge(T, X, Z);
Merge(T, T, Y);
return ;
}
void DFS(Node * T)
{
if (!T)
return ;
DFS(T->l);
rev[T->id] = ++ tscnt;
DFS(T->r);
}
pair < int , int > Query(Node * T, int id)
{
assert(T);
if (T->id == id)
return make_pair(T->a[0], T->a[1]);
if (T->id < id)
return Query(T->r, id);
return Query(T->l, id);
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= m; i ++)
scanf("%d%d", &A[i], &B[i]),
U.push_back(A[i]),
U.push_back(B[i]);
int tsm = m;
for (int i = 1; i <= q; i ++)
{
scanf("%d", &TP[i]);
if (TP[i] == 1) scanf("%d", &L[i]);
if (TP[i] == 2) scanf("%d", &L[i]), U.push_back(L[i]), U.push_back(n - L[i]);
if (TP[i] == 3) scanf("%d", &L[i]), U.push_back(L[i]), U.push_back(n - L[i]), Sub2 = 0;
if (TP[i] == 4) tsm ++, scanf("%d%d", &A[tsm], &B[tsm]), U.push_back(A[tsm]), U.push_back(B[tsm]), Sub4 = 1;
}
assert(Sub4 == 0);
sort(U.begin(), U.end());
U.resize(unique(U.begin(), U.end()) - U.begin());
for (int i = 1; i <= tsm; i ++)
{
A[i] = lower_bound(U.begin(), U.end(), A[i]) - U.begin();
B[i] = lower_bound(U.begin(), U.end(), B[i]) - U.begin();
}
for (int i = 1; i <= q; i ++)
if (TP[i] == 2 || TP[i] == 3)
nL[i] = lower_bound(U.begin(), U.end(), n - L[i]) - U.begin(),
L[i] = lower_bound(U.begin(), U.end(), L[i]) - U.begin();
fill(Last, Last + MXN, q + 1);
for (int i = q; i; i --)
{
if (TP[i] != 2 && TP[i] != 3)
continue;
if (TP[i] == 2)
Last[L[i]] = i;
if (TP[i] == 3)
Last[nL[i]] = i;
}
for (int i = 0; i < (int)U.size(); i ++)
MN[i + MXN] = Last[i];
for (int i = MXN - 1; i; i --)
MN[i] = min(MN[i << 1], MN[i << 1 ^ 1]);
for (int i = 1; i <= m; i ++)
{
int l = B[i];
int r = upper_bound(U.begin(), U.end(), n - A[i]) - U.begin();
ST[i] = GetMin(l, r);
V[ST[i]].push_back(i);
}
Node * T = NULL;
for (int i = 1; i <= q; i ++)
{
if (TP[i] == 1)
{
if (ST[L[i]] > i)
Res[i] = {A[L[i]], B[L[i]]};
continue;
}
if (TP[i] == 2)
{
int a[2] = {nL[i], 0};
Add(T, L[i], nL[i], a);// [y, x]
}
if (TP[i] == 3)
{
int a[2] = {0, nL[i]};
Add(T, nL[i], L[i], a);// [y, x]
}
for (int j : V[i])
{
int a = A[j], b = B[j];
if (TP[i] == 2)
a = max(a, nL[i]);
if (TP[i] == 3)
b = max(b, nL[i]);
Insert(T, a, b, j);
}
}
DFS(T);
T = NULL;
for (int i = 1; i <= q; i ++)
{
if (TP[i] == 1)
{
if (ST[L[i]] > i)
Res[i] = {A[L[i]], B[L[i]]};
else
Res[i] = Query(T, rev[L[i]]);
continue;
}
if (TP[i] == 2)
{
int a[2] = {nL[i], 0};
Add(T, L[i], nL[i], a);// [y, x]
}
if (TP[i] == 3)
{
int a[2] = {0, nL[i]};
Add(T, nL[i], L[i], a);// [y, x]
}
for (int j : V[i])
{
int a = A[j], b = B[j];
if (TP[i] == 2)
a = max(a, nL[i]);
if (TP[i] == 3)
b = max(b, nL[i]);
Insert(T, a, b, rev[j]);
}
}
for (int i = 1; i <= q; i ++)
if (TP[i] == 1)
{
printf("%d %d\n", U[Res[i].first], U[Res[i].second]);
}
return 0;
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &m, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:118:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &A[i], &B[i]),
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
U.push_back(A[i]),
~~~~~~~~~~~~~~~~~^~
U.push_back(B[i]);
~~~~~~~~~~~~~~~~~
sweeping.cpp:123:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &TP[i]);
~~~~~^~~~~~~~~~~~~~
sweeping.cpp:124:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
if (TP[i] == 1) scanf("%d", &L[i]);
~~~~~^~~~~~~~~~~~~
sweeping.cpp:125:70: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
if (TP[i] == 2) scanf("%d", &L[i]), U.push_back(L[i]), U.push_back(n - L[i]);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:126:93: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
if (TP[i] == 3) scanf("%d", &L[i]), U.push_back(L[i]), U.push_back(n - L[i]), Sub2 = 0;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
sweeping.cpp:127:114: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
if (TP[i] == 4) tsm ++, scanf("%d%d", &A[tsm], &B[tsm]), U.push_back(A[tsm]), U.push_back(B[tsm]), Sub4 = 1;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
48376 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 |
555 ms |
89716 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 |
Execution timed out |
18086 ms |
101592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18086 ms |
101592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
48376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
