#include<bits/stdc++.h>
using namespace std;
const int maxm = 2 * 1500100;
const int maxq = 2 * 1000100;
struct dust
{
int x, y, idx;
}d[maxm];
bool cmp_y(dust d1, dust d2)
{
return d1.y < d2.y;
}
struct query
{
int t, p, l, a, b, idx;
}task[maxq];
int n, m, q;
void input()
{
cin >> n >> m >> q;
for (int i = 1; i <= m; i ++)
{
cin >> d[i].x >> d[i].y;
d[i].idx = i;
}
for (int i = 1; i <= q; i ++)
{
cin >> task[i].t;
if (task[i].t == 1)
cin >> task[i].p;
else
if (task[i].t == 2 || task[i].t == 3)
cin >> task[i].l;
else
{
cin >> task[i].a >> task[i].b;
d[++ m].idx = m;
task[i].idx = m;
d[m].x = task[i].a;
d[m].y = task[i].b;
}
}
}
void solve_slow()
{
for (int i = 1; i <= q; i ++)
{
if (task[i].t == 1)
{
cout << d[task[i].p].x << " " << d[task[i].p].y << endl;
}
else
if (task[i].t == 2)
{
for (int j = 1; j <= m; j ++)
{
if (d[j].x < n - task[i].l && d[j].y <= task[i].l)
d[j].x = n - task[i].l;
}
}
else
if (task[i].t == 3)
{
for (int j = 1; j <= m; j ++)
{
if (d[j].x <= task[i].l && d[j].y < n - task[i].l)
d[j].y = n - task[i].l;
}
}
else
{
d[task[i].idx].x = task[i].a;
d[task[i].idx].y = task[i].b;
}
}
}
const int inf = 1e9 + 10;
struct node
{
int min_num, sec_num;
node(int _min_num = inf, int _sec_num = inf)
{
min_num = _min_num;
sec_num = _sec_num;
}
};
node merge_node(node lf, node rf)
{
node mf = lf;
if (rf.min_num < mf.min_num)
{
mf.sec_num = mf.min_num;
mf.min_num = rf.min_num;
}
else
if (rf.min_num < mf.sec_num && rf.min_num != mf.min_num)
{
mf.sec_num = rf.min_num;
}
if (rf.sec_num < mf.min_num)
{
mf.sec_num = mf.min_num;
mf.min_num = rf.sec_num;
}
else
if (rf.sec_num < mf.sec_num && rf.sec_num != mf.min_num)
{
mf.sec_num = rf.sec_num;
}
return mf;
};
int lazy[4 * maxm];
node tree[4 * maxm];
void push_lazy(int root, int left, int right)
{
if (lazy[root] == 0)
return;
if (tree[root].min_num < lazy[root])
tree[root].min_num = lazy[root];
///cout << "push lazy " << root << " " << left << " " << right << " " << lazy[root] << endl;
if (left != right)
{
lazy[root * 2] = max(lazy[root * 2], lazy[root]);
lazy[root * 2 + 1] = max(lazy[root * 2 + 1], lazy[root]);
}
lazy[root] = 0;
}
void update_range(int root, int left, int right, int qleft, int qright, int val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft && tree[root].min_num >= val)
return;
if (left >= qleft && right <= qright && tree[root].sec_num > val)
{
//cout << "update node " << left << " " << right << " " << tree[root].min_num << " " << tree[root].sec_num << endl;
lazy[root] = val;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
update_range(root * 2, left, mid, qleft, qright, val);
update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
///cout << "tree " << root << " " << left << " " << right << " " << tree[root].min_num << " " << tree[root].sec_num << endl;
}
void update_point(int root, int left, int right, int pos, int val)
{
push_lazy(root, left, right);
if (left == right)
{
tree[root].min_num = val;
tree[root].sec_num = inf;
return;
}
int mid = (left + right) / 2;
if (pos <= mid)
update_point(root * 2, left, mid, pos, val);
else
update_point(root * 2 + 1, mid + 1, right, pos, val);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
int query(int root, int left, int right, int pos)
{
push_lazy(root, left, right);
if (left == right)
{
//cout << "query " << left << " " << right << " " << tree[root].min_num << endl;
return tree[root].min_num;
}
int mid = (left + right) / 2;
if (pos <= mid)
return query(root * 2, left, mid, pos);
return query(root * 2 + 1, mid + 1, right, pos);
}
void build_tree(int root, int left, int right)
{
if (left == right)
{
tree[root].min_num = d[left].x;
tree[root].sec_num = inf;
//cout << "tree " << root << " " << left << " " << right << " " << tree[root].min_num << " " << tree[root].sec_num << endl;
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
///cout << "tree " << root << " " << left << " " << right << " " << tree[root].min_num << " " << tree[root].sec_num << endl;
}
int rev[maxm];
void solve_second()
{
sort(d + 1, d + m + 1, cmp_y);
for (int i = 1; i <= m; i ++)
rev[d[i].idx] = i;
build_tree(1, 1, m);
for (int i = 1; i <= q; i ++)
{
if (task[i].t == 1)
{
task[i].p = rev[task[i].p];
cout << query(1, 1, m, task[i].p) << " " << d[task[i].p].y << endl;
}
else
if (task[i].t == 2)
{
int lf = 1, rf = m;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (d[mf].y <= task[i].l)
lf = mf + 1;
else
rf = mf - 1;
}
update_range(1, 1, m, 1, rf, n - task[i].l);
}
else
if (task[i].t == 3)
{
assert(false);
}
else
if (task[i].t == 4)
{
task[i].idx = rev[task[i].idx];
update_point(1, 1, m, task[i].idx, task[i].a);
}
}
}
void solve()
{
input();
///cout << "----------" << endl;
//if (m <= 7000 && q <= 5000)
// solve_slow();
//else
solve_second();
}
int main()
{
solve();
return 0;
}
Compilation message
sweeping.cpp: In function 'void input()':
sweeping.cpp:45:15: warning: operation on 'm' may be undefined [-Wsequence-point]
45 | d[++ m].idx = m;
| ^~~~
sweeping.cpp:45:15: warning: operation on 'm' may be undefined [-Wsequence-point]
sweeping.cpp: In function 'void update_range(int, int, int, int, int, int)':
sweeping.cpp:152:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
152 | if (left > qright || right < qleft && tree[root].min_num >= val)
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
101 ms |
204368 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2060 ms |
161536 KB |
Output is correct |
| 2 |
Correct |
2053 ms |
161376 KB |
Output is correct |
| 3 |
Correct |
2076 ms |
161324 KB |
Output is correct |
| 4 |
Correct |
1894 ms |
160556 KB |
Output is correct |
| 5 |
Correct |
2302 ms |
171232 KB |
Output is correct |
| 6 |
Correct |
1873 ms |
171268 KB |
Output is correct |
| 7 |
Correct |
2136 ms |
171648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
790 ms |
267136 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
790 ms |
267136 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
101 ms |
204368 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
