#include <bits/stdc++.h>
using namespace std;
constexpr size_t M = 500000;
uint32_t compare_mode = 0;
struct segment
{
int32_t i1, i2, x1, x2, y1, y2;
bool operator<(segment const &s) const
{
return !compare_mode ? i1 < s.i1 : (compare_mode == 1 ? x1 < s.x1 : y1 > s.y1);
}
};
set<segment> s;
pair<int32_t, int32_t> p[M];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int64_t n, m, q;
cin >> n >> m >> q;
for (int32_t i = 0; i < m; ++i)
{
cin >> p[i].first >> p[i].second;
segment t = {i, i, p[i].first, p[i].first, p[i].second, p[i].second};
if (!s.empty())
{
auto it = --s.end();
if (it->x1 == it->x2 && it->x2 == p[i].first)
{
t.y2 = it->y2;
t.i1 = it->i1;
s.erase(it);
}
else if (it->y1 == it->y2 && it->y2 == p[i].second)
{
t.x1 = it->x1;
t.i1 = it->i1;
s.erase(it);
}
}
s.insert(t);
}
while (q--)
{
size_t t;
cin >> t;
if (t == 1)
{
int32_t i;
cin >> i, --i;
compare_mode = 0;
auto it = prev(s.upper_bound((segment){i, i, 0, 0, 0, 0}));
cout << max(it->x1, p[i].first) << ' ' << max(it->y1, p[i].second) << '\n';
}
else if (t == 2)
{
int32_t l;
cin >> l;
compare_mode = 2;
auto it = s.lower_bound((segment){0, 0, 0, 0, l, l});
segment t = {INT32_MAX, -1, n - l, n - l, INT32_MAX, -1};
while (it != s.end() && it->x1 <= n - l)
{
t.y1 = min(t.y1, it->y1);
t.y2 = max(t.y2, it->y2);
if (it->x2 <= n - l)
{
t.i1 = min(t.i1, it->i1);
t.i2 = max(t.i2, it->i2);
it = s.erase(it);
}
else
{
int32_t a = it->i1, b = it->i2;
while (a < b)
{
size_t const mid = (a + b + 1) / 2;
if (max(p[mid].first, it->x1) > n - l)
b = mid - 1;
else
a = mid;
}
t.i1 = min(t.i1, it->i1);
t.i2 = max(t.i2, a);
if (a != it->i2)
{
segment u = {a + 1, it->i2, p[a + 1].first, it->x2, it->y1, it->y1};
s.erase(it);
s.insert(u);
}
else
{
s.erase(it);
}
break;
}
}
if (t.i1 != INT32_MAX)
s.insert(t);
}
else if (t == 3)
{
int32_t l;
cin >> l;
compare_mode = 1;
auto it = s.upper_bound((segment){0, 0, l, l, 0, 0});
if (it == s.begin())
continue;
--it;
segment t = {INT32_MAX, -1, INT32_MAX, -1, n - l, n - l};
while (it->y1 <= n - l)
{
t.x1 = min(t.x1, it->x1);
t.x2 = max(t.x2, it->x2);
if (t.y2 <= n - l)
{
t.i1 = min(t.i1, it->i1);
t.i2 = max(t.i2, it->i2);
it = s.erase(it);
if (it == s.begin())
break;
--it;
}
else
{
int32_t a = it->i1, b = it->i2;
while (a < b)
{
size_t const mid = (a + b) / 2;
if (max(p[mid].second, it->y1) >= n - l)
b = mid;
else
a = mid + 1;
}
t.i1 = min(t.i1, a);
t.i2 = max(t.i2, it->i2);
if (a != it->i1)
{
segment u = {it->i1, a - 1, it->x1, it->x1, it->y1, p[a - 1].second};
s.erase(it);
s.insert(u);
}
else
{
s.erase(it);
}
break;
}
}
if (t.i1 != INT32_MAX)
s.insert(t);
}
else
{
}
}
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:70:43: warning: narrowing conversion of '(n - ((int64_t)l))' from 'int64_t' {aka 'long int'} to 'int32_t' {aka 'int'} [-Wnarrowing]
70 | segment t = {INT32_MAX, -1, n - l, n - l, INT32_MAX, -1};
| ~~^~~
sweeping.cpp:70:50: warning: narrowing conversion of '(n - ((int64_t)l))' from 'int64_t' {aka 'long int'} to 'int32_t' {aka 'int'} [-Wnarrowing]
70 | segment t = {INT32_MAX, -1, n - l, n - l, INT32_MAX, -1};
| ~~^~~
sweeping.cpp:119:58: warning: narrowing conversion of '(n - ((int64_t)l))' from 'int64_t' {aka 'long int'} to 'int32_t' {aka 'int'} [-Wnarrowing]
119 | segment t = {INT32_MAX, -1, INT32_MAX, -1, n - l, n - l};
| ~~^~~
sweeping.cpp:119:65: warning: narrowing conversion of '(n - ((int64_t)l))' from 'int64_t' {aka 'long int'} to 'int32_t' {aka 'int'} [-Wnarrowing]
119 | segment t = {INT32_MAX, -1, INT32_MAX, -1, n - l, n - l};
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
251 ms |
72104 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
516 ms |
45484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
516 ms |
45484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
