제출 #217819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
217819		tincamatei	청소 (JOI20_sweeping)	C++14	100 / 100	8820 ms	821764 KiB

sweeping

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000000;
const int MAX_M = 500000;
const int MAX_Q = 1000000;
const int MAX_R = MAX_M + MAX_Q;

int lastDSUNodeId = 0;
struct DSUNode {
	int sef, val, rank, assignedRange;
	vector<int> graph;
};

vector<DSUNode> dsu;

// find the boss of 'nod'
// O(logN)
int myfind(int nod) {
	if(dsu[nod].sef == nod)
		return nod;
	return myfind(dsu[nod].sef);
}

// Unite node 'a' and node 'b'
// Union by rank
// O(logN)
int myunion(int a, int b) {
	int sa = myfind(a), sb = myfind(b);

	if(sa != sb) {
		if(dsu[sa].rank < dsu[sb].rank) {
			dsu[sa].sef = sb;
			dsu[sb].graph.push_back(sa);
			return sb;
		} else {
			dsu[sb].sef = sa;
			dsu[sa].graph.push_back(sb);
			if(dsu[sa].rank == dsu[sb].rank)
				dsu[sa].rank++;
			return sa;
		}
	}
	return sa;
}

struct QueryRange {
	int leftHead, rightHead;
} ranges[1+MAX_R];

// Put the ranges of the nodes assigned to the tree of 'nod' into vector 'target'
void unpackTree(int nod, vector<int> &target) {
	dsu[nod].val = dsu[dsu[nod].sef].val;
	
	if(nod == ranges[dsu[nod].assignedRange].leftHead ||
	   nod == ranges[dsu[nod].assignedRange].rightHead)
		target.push_back(dsu[nod].assignedRange);
	
	for(auto it: dsu[nod].graph)
		unpackTree(it, target);
	dsu[nod].graph.clear();
}

// Assign a new dsu node
int assignDSUNode(int rangeId) {
	dsu.push_back({0, 0, 0, 0});
	lastDSUNodeId++;
	return lastDSUNodeId - 1;
}

struct SegTree {
	SegTree* left;
	SegTree* right;
	
	SegTree() {
		left = right = NULL;
	}

	set<pair<int, int> > leftHalf;
	set<pair<int, int> > rightHalf;
};

SegTree* segtree = NULL;

// Insert a range in the segment tree
void insertRange(SegTree* &T, int id, int x, int y, int l = 0, int r = MAX_N) {
	int mid = (l + r) / 2;

	if(T == NULL)
		T = new SegTree();

	if(x <= mid && mid + 1 <= y) { // Here is the current range's place
		T->leftHalf.insert({x, ranges[id].leftHead});
		T->rightHalf.insert({y, ranges[id].rightHead});
	} else if(l < r) {
		if(y <= mid)
			insertRange(T->left, id, x, y, l, mid);
		else
			insertRange(T->right, id, x, y, mid + 1, r);
	}
}

// Cut all values greater than or equal to val from given set
// return their union
void setCutRight(set<pair<int, int> > &myset, int val, vector<int> &target) {
	while(!myset.empty() && myset.rbegin()->first >= val) {
		target.push_back(myset.rbegin()->second);
		myset.erase(*myset.rbegin());
	}
}

// Cut all values less than or equal to val from given set
// return their union
void setCutLeft(set<pair<int, int> > &myset, int val, vector<int> &target) {
	while(!myset.empty() && myset.begin()->first <= val) {
		target.push_back(myset.begin()->second);
		myset.erase(*myset.begin());
	}
}

// Cut ranges in segment tree by x or y. If one of them is -1, that update
// is disabled. One of the updates must be disabled
// Put all ranges in target
void pickupIntersecting(SegTree* &T, int x, int y, vector<int> &target,
                        int l = 0, int r = MAX_N) {
	int mid = (l + r) / 2;
	if(T == NULL)
		return;
	if(x != -1 && (x < l || r < x))
		return;
	if(y != -1 && (y < l || r < y))
		return;
	if(l < r) {
		if(x != -1) {
			if(x <= mid) { // Cut lefties
				vector<int> lefties;
				setCutLeft(T->leftHalf, x, lefties);
				
				int newNode = -1;
				for(int i = 0; i < lefties.size(); ++i)
					if(i > 0)
						newNode = myunion(lefties[i - 1], lefties[i]);
					else
						newNode = lefties[i];
				if(newNode != -1) {
					dsu[newNode].val = x;
					T->leftHalf.insert(make_pair(dsu[newNode].val, newNode));
				}
			} else { // Get rid of lefties
				vector<int> nodes;
				setCutRight(T->rightHalf, x, nodes);
				
				for(int i = 0; i < nodes.size(); ++i)
					unpackTree(nodes[i], target);
			}
		} else if(y != -1) {
			if(y > mid) {
				vector<int> righties;
				setCutRight(T->rightHalf, y, righties);

				int newNode = -1;
				for(int i = 0; i < righties.size(); ++i) {
					if(i > 0)
						newNode = myunion(righties[i - 1], righties[i]);
					else
						newNode = righties[i];
				}

				if(newNode != -1) {
					dsu[newNode].val = y;
					T->rightHalf.insert(make_pair(dsu[newNode].val, newNode));
				}
			} else {
				vector<int> nodes;
				setCutLeft(T->leftHalf, y, nodes);
				
				for(int i = 0; i < nodes.size(); ++i) {
					unpackTree(nodes[i], target);
				}
			}
		}

		pickupIntersecting(T->left, x, y, target, l, mid);
		pickupIntersecting(T->right, x, y, target, mid + 1, r);
	}
}

pair<int, int> queryRange(int rangeId) {
	pair<int, int> rez;
	int a = ranges[rangeId].leftHead;
	int b = ranges[rangeId].rightHead;

	a = myfind(a);
	b = myfind(b);

	rez = make_pair(dsu[a].val, dsu[b].val);
	return rez;
}

void segTreeInsertRange(int x, int y, int id) {
	ranges[id].leftHead = assignDSUNode(id);
	ranges[id].rightHead = assignDSUNode(id);
	dsu[ranges[id].leftHead] = {ranges[id].leftHead, x, 0, id};
	dsu[ranges[id].rightHead] = {ranges[id].rightHead, y, 0, id};
	
	insertRange(segtree, id, x, y);
}

// Cut the ranges with lUpd or rUpd
// If an update is -1, that means that there will be no update
void updateRange(int lUpd, int rUpd) {
	vector<int> updatedRanges;
	pickupIntersecting(segtree, lUpd, rUpd, updatedRanges);

	for(auto it: updatedRanges) {
		pair<int, int> oldRange = queryRange(it);
		int x, y;
		x = oldRange.first;
		y = oldRange.second;
		if(lUpd != -1)
			x = lUpd;
		if(rUpd != -1)
			y = rUpd;
		segTreeInsertRange(x, y, it);
	}
}

int lastRangeId = 0;
void addRange(int x, int y) {
	++lastRangeId;

	segTreeInsertRange(x, y, lastRangeId);
}

int main() {
	int N, M, Q;

	scanf("%d%d%d", &N, &M, &Q);

	for(int i = 0; i < M; ++i) {
		int X, Y;
		scanf("%d%d", &X, &Y);
		addRange(X, N - Y);
	}

	for(int i = 0; i < Q; ++i) {
		int T;
		scanf("%d", &T);

		if(T == 1) {
			int P;
			scanf("%d", &P);
			pair<int, int> rez = queryRange(P);
			printf("%d %d\n", rez.first, N - rez.second);
		} else if(T == 2) {
			int L;
			scanf("%d", &L);
			updateRange(N - L, -1);
		} else if(T == 3) {
			int L;
			scanf("%d", &L);
			updateRange(-1, L);
		} else {
			int A, B;
			scanf("%d%d", &A, &B);
			addRange(A, N - B);
		}
	}

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

sweeping.cpp: In function 'void pickupIntersecting(SegTree*&, int, int, std::vector<int>&, int, int)':
sweeping.cpp:141:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < lefties.size(); ++i)
                    ~~^~~~~~~~~~~~~~~~
sweeping.cpp:154:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < nodes.size(); ++i)
                    ~~^~~~~~~~~~~~~~
sweeping.cpp:163:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < righties.size(); ++i) {
                    ~~^~~~~~~~~~~~~~~~~
sweeping.cpp:178:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < nodes.size(); ++i) {
                    ~~^~~~~~~~~~~~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:239:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:243:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &X, &Y);
   ~~~~~^~~~~~~~~~~~~~~~
sweeping.cpp:249:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &T);
   ~~~~~^~~~~~~~~~
sweeping.cpp:253:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &P);
    ~~~~~^~~~~~~~~~
sweeping.cpp:258:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &L);
    ~~~~~^~~~~~~~~~
sweeping.cpp:262:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &L);
    ~~~~~^~~~~~~~~~
sweeping.cpp:266:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &A, &B);
    ~~~~~^~~~~~~~~~~~~~~~

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