#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 15e5;
int n, m, q;
pii interval[MAXN];
class group {
public:
set<int> vals;
int pos;
group(int a, int b) {
vals.insert(a);
pos = b;
}
int size() {
return vals.size();
}
void insert(int a) {
vals.insert(a);
}
void erase(int a) {
vals.erase(a);
}
void clear() {
vals.clear();
}
};
vector<group> groups;
int lgroup[MAXN];
int rgroup[MAXN];
int merge(int a, int b, int garr[]) {
if (groups[a].size() < groups[b].size()) swap(a, b);
for (int v: groups[b].vals) {
groups[a].insert(v);
garr[v] = a;
}
groups[b].clear();
return a;
}
class stree {
public:
priority_queue<pii> lvals;
priority_queue<pii, vector<pii>, greater<pii>> rvals;
int lp, rp;
int mid;
stree *l = nullptr;
stree *r = nullptr;
stree(int lp, int rp) : lp(lp), rp(rp) {
mid = (lp+rp)/2;
}
void ins(int i) {
if (interval[i].second < mid) {
if (!l) l = new stree(lp, mid-1);
l->ins(i);
}
else if (interval[i].first > mid) {
if (!r) r = new stree(mid+1, rp);
r->ins(i);
}
else {
groups.push_back(group(i, interval[i].first));
groups.push_back(group(i, interval[i].second));
lgroup[i] = groups.size()-2;
rgroup[i] = groups.size()-1;
lvals.push(pii(interval[i].first, lgroup[i]));
rvals.push(pii(interval[i].second, rgroup[i])); // could merge but not necessary
}
}
void lalign(int p) { // move l to this pos
if (p > mid) {
if (r) r->lalign(p);
while (!rvals.empty() && rvals.top().first >= p) {
pii tp = rvals.top();
rvals.pop();
// if (tp.second == 3) {
// cerr << groups[3].pos << '\n';
// for (int v: groups[3].vals) cerr << v << ' ';
// cerr << '\n';
// }
for (auto it = groups[tp.second].vals.begin(); it != groups[tp.second].vals.end(); it++) {
int v = *it;
interval[v].first = p;
interval[v].second = groups[rgroup[v]].pos;
groups[lgroup[v]].erase(v);
if (!r) r = new stree(mid+1, rp);
r->ins(v);
}
groups[tp.second].clear();
}
}
else {
if (p < mid && l) l->lalign(p);
int merged = -1;
while (!lvals.empty() && lvals.top().first <= p) {
pii tp = lvals.top();
lvals.pop();
if (merged == -1) merged = tp.second;
else {
merged = merge(tp.second, merged, lgroup);
}
}
if (merged != -1) {
lvals.push(pii(p, merged));
groups[merged].pos = p;
}
}
}
void ralign(int p) { // move r to this pos
if (p < mid) {
if (l) l->ralign(p);
while (!lvals.empty() && lvals.top().first <= p) {
pii tp = lvals.top();
lvals.pop();
for (auto it = groups[tp.second].vals.begin(); it != groups[tp.second].vals.end(); it++) {
int v = *it;
interval[v].second = p;
interval[v].first = groups[lgroup[v]].pos;
groups[rgroup[v]].erase(v);
if (!l) l = new stree(lp, mid-1);
l->ins(v);
}
groups[tp.second].clear();
}
}
else {
if (p > mid && r) r->ralign(p);
int merged = -1;
while (!rvals.empty() && rvals.top().first >= p) {
pii tp = rvals.top();
rvals.pop();
if (merged == -1) merged = tp.second;
else {
merged = merge(tp.second, merged, rgroup);
}
}
if (merged != -1) {
rvals.push(pii(p, merged));
groups[merged].pos = p;
}
}
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m >> q;
stree *tree = new stree(0, n+1);
for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
interval[i] = pii(x, n-y);
tree->ins(i);
}
for (int i = 0; i < q; i++) {
int t; cin >> t;
if (t == 1) {
int p;
cin >> p; p--;
cout << groups[lgroup[p]].pos << ' ' << (n-groups[rgroup[p]].pos) << '\n';
}
if (t == 2) {
int l; cin >> l;
tree->lalign(n-l);
}
if (t == 3) {
int l; cin >> l;
tree->ralign(l);
}
if (t == 4) {
int x, y; cin >> x >> y;
interval[m] = pii(x, n-y);
tree->ins(m++);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2274 ms |
490912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1640 ms |
578344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1640 ms |
578344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
