oj.uz

Submission #217819

# Submission time Handle Problem Language Result Execution time Memory
217819 2020-03-30T21:35:57 Z tincamatei Sweeping (JOI20_sweeping) C++14
100 / 100
 8820 ms 821764 KB 
#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;
}

Compilation message

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2072 KB Output is correct
2 Correct 10 ms 896 KB Output is correct
3 Correct 10 ms 1116 KB Output is correct
4 Correct 15 ms 2072 KB Output is correct
5 Correct 20 ms 2068 KB Output is correct
6 Correct 9 ms 896 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4536 ms 583240 KB Output is correct
2 Correct 4086 ms 447284 KB Output is correct
3 Correct 4085 ms 446688 KB Output is correct
4 Correct 3052 ms 314104 KB Output is correct
5 Correct 7920 ms 809832 KB Output is correct
6 Correct 6176 ms 487144 KB Output is correct
7 Correct 4098 ms 428488 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4066 ms 412192 KB Output is correct
2 Correct 3981 ms 416104 KB Output is correct
3 Correct 1589 ms 217812 KB Output is correct
4 Correct 5359 ms 803376 KB Output is correct
5 Correct 4149 ms 425340 KB Output is correct
6 Correct 3069 ms 394312 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4066 ms 412192 KB Output is correct
2 Correct 3981 ms 416104 KB Output is correct
3 Correct 1589 ms 217812 KB Output is correct
4 Correct 5359 ms 803376 KB Output is correct
5 Correct 4149 ms 425340 KB Output is correct
6 Correct 3069 ms 394312 KB Output is correct
7 Correct 3811 ms 394036 KB Output is correct
8 Correct 3959 ms 373180 KB Output is correct
9 Correct 4024 ms 375528 KB Output is correct
10 Correct 2744 ms 311748 KB Output is correct
11 Correct 6176 ms 426544 KB Output is correct
12 Correct 6231 ms 397044 KB Output is correct
13 Correct 6125 ms 405948 KB Output is correct
14 Correct 625 ms 4216 KB Output is correct
15 Correct 1822 ms 111688 KB Output is correct
16 Correct 3696 ms 359484 KB Output is correct
17 Correct 3765 ms 364208 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2072 KB Output is correct
2 Correct 10 ms 896 KB Output is correct
3 Correct 10 ms 1116 KB Output is correct
4 Correct 15 ms 2072 KB Output is correct
5 Correct 20 ms 2068 KB Output is correct
6 Correct 9 ms 896 KB Output is correct
7 Correct 4536 ms 583240 KB Output is correct
8 Correct 4086 ms 447284 KB Output is correct
9 Correct 4085 ms 446688 KB Output is correct
10 Correct 3052 ms 314104 KB Output is correct
11 Correct 7920 ms 809832 KB Output is correct
12 Correct 6176 ms 487144 KB Output is correct
13 Correct 4098 ms 428488 KB Output is correct
14 Correct 4066 ms 412192 KB Output is correct
15 Correct 3981 ms 416104 KB Output is correct
16 Correct 1589 ms 217812 KB Output is correct
17 Correct 5359 ms 803376 KB Output is correct
18 Correct 4149 ms 425340 KB Output is correct
19 Correct 3069 ms 394312 KB Output is correct
20 Correct 3811 ms 394036 KB Output is correct
21 Correct 3959 ms 373180 KB Output is correct
22 Correct 4024 ms 375528 KB Output is correct
23 Correct 2744 ms 311748 KB Output is correct
24 Correct 6176 ms 426544 KB Output is correct
25 Correct 6231 ms 397044 KB Output is correct
26 Correct 6125 ms 405948 KB Output is correct
27 Correct 625 ms 4216 KB Output is correct
28 Correct 1822 ms 111688 KB Output is correct
29 Correct 3696 ms 359484 KB Output is correct
30 Correct 3765 ms 364208 KB Output is correct
31 Correct 3691 ms 438064 KB Output is correct
32 Correct 4438 ms 606720 KB Output is correct
33 Correct 2545 ms 768128 KB Output is correct
34 Correct 5372 ms 585272 KB Output is correct
35 Correct 5299 ms 584880 KB Output is correct
36 Correct 3111 ms 305132 KB Output is correct
37 Correct 8820 ms 821764 KB Output is correct
38 Correct 7677 ms 780484 KB Output is correct
39 Correct 6050 ms 407732 KB Output is correct
40 Correct 4001 ms 409772 KB Output is correct