| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 740603 |
2023-05-12T19:03:11 Z |
finn__ |
Sweeping (JOI20_sweeping) |
C++17 |
|
2003 ms |
546168 KB |
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define M 500000
#define Q 1000000
struct triangle
{
Tree<array<uint32_t, 3>> x, y;
uint32_t a, b;
};
uint32_t p[M][2], ind[M], l;
triangle tr[Q + 1];
bool compare_mode = 1;
bool compare_triangle(size_t const &a, size_t const &b)
{
return !compare_mode ? tr[a].a < tr[b].a : tr[a].b > tr[b].b;
};
set<size_t, decltype(&compare_triangle)> s;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t n, m, q;
cin >> n >> m >> q;
for (uint32_t i = 0; i < m; ++i)
{
cin >> p[i][0] >> p[i][1];
tr[0].x.insert({p[i][0], p[i][1], i});
tr[0].y.insert({p[i][1], p[i][0], i});
}
s = set<size_t, decltype(&compare_triangle)>(&compare_triangle);
s.insert(0);
l = 1;
while (q--)
{
size_t t;
cin >> t;
if (t == 1)
{
size_t i;
cin >> i, --i;
cout << max(p[i][0], tr[ind[i]].a) << ' ' << max(p[i][1], tr[ind[i]].b) << '\n';
}
else if (t == 2)
{
uint32_t L;
cin >> L;
tr[Q].b = L;
compare_mode = 1;
auto it = s.lower_bound(Q);
triangle &t = tr[l++], &u = tr[*it];
if (u.y.order_of_key({L, UINT32_MAX, UINT32_MAX}) < u.y.size() / 2)
{
t.a = n - L;
t.b = u.b;
u.b = L;
for (auto jt = u.y.begin(); jt != u.y.end() && (*jt)[0] <= L; jt = u.y.erase(jt))
{
t.x.insert({(*jt)[1], (*jt)[0], (*jt)[2]});
t.y.insert(*jt);
ind[(*jt)[2]] = l - 1;
u.x.erase({(*jt)[1], (*jt)[0], (*jt)[2]});
}
}
else
{
t.a = u.a;
u.a = n - L;
t.b = L;
for (auto jt = u.y.rbegin(); jt != u.y.rend() && (*jt)[0] > L;)
{
t.x.insert({(*jt)[1], (*jt)[0], (*jt)[2]});
t.y.insert(*jt);
ind[(*jt)[2]] = l - 1;
u.x.erase({(*jt)[1], (*jt)[0], (*jt)[2]});
jt = u.y.erase(jt);
if (jt != u.y.rend())
--jt;
}
}
s.insert(l - 1);
}
else if (t == 3)
{
uint32_t L;
cin >> L;
tr[Q].a = L;
compare_mode = 0;
auto it = prev(s.upper_bound(Q));
triangle &t = tr[l++], &u = tr[*it];
if (u.x.order_of_key({L, UINT32_MAX, UINT32_MAX}) < u.x.size() / 2)
{
t.a = u.a;
t.b = n - L;
u.a = L;
for (auto jt = u.x.begin(); jt != u.x.end() && (*jt)[0] <= L; jt = u.x.erase(jt))
{
t.y.insert({(*jt)[1], (*jt)[0], (*jt)[2]});
t.x.insert(*jt);
ind[(*jt)[2]] = l - 1;
u.y.erase({(*jt)[1], (*jt)[0], (*jt)[2]});
}
}
else
{
t.a = L;
t.b = u.b;
u.b = n - L;
for (auto jt = u.x.rbegin(); jt != u.x.rend() && (*jt)[0] > L;)
{
t.y.insert({(*jt)[1], (*jt)[0], (*jt)[2]});
t.x.insert(*jt);
ind[(*jt)[2]] = l - 1;
u.y.erase({(*jt)[1], (*jt)[0], (*jt)[2]});
jt = u.x.erase(jt);
if (jt != u.x.rend())
--jt;
}
}
s.insert(l - 1);
}
else
{
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
144 ms |
196424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2003 ms |
546168 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1841 ms |
315836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1841 ms |
315836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
144 ms |
196424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
