Submission #709594

#	Time	Username	Problem	Language	Result	Execution time	Memory
709594		GusterGoose27	Sweeping (JOI20_sweeping)	C++17	0 / 100	2274 ms	578344 KiB

sweeping

#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++);
		}
	}
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25