oj.uz

Submission #44360

# Submission time Handle Problem Language Result Execution time Memory
44360 2018-03-31T18:03:33 Z JustInCase Plahte (COCI17_plahte) C++17
160 / 160
 1085 ms 469144 KB 
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int32_t MAX_N = 80005;
const int32_t MAX_M = 80005;

class Rectangle {
public:
	int32_t lowerLeftX, lowerLeftY, upperRightX, upperRightY, ind;
};

class Shot {
public:
	int32_t x, y, color;	
};

Rectangle rects[MAX_N];
Shot shots[MAX_M];

void Compress(int32_t n, int32_t m, int32_t &maxY) {
	vector< int32_t > xs, ys;
	xs.push_back(0);
	ys.push_back(0);

	for(int32_t i = 1; i <= n; i++) {
		xs.push_back(rects[i].lowerLeftX);
		xs.push_back(rects[i].upperRightX);
		ys.push_back(rects[i].lowerLeftY);
		ys.push_back(rects[i].upperRightY);
	}

	for(int32_t i = 1; i <= m; i++) {
		xs.push_back(shots[i].x);
		ys.push_back(shots[i].y);
	}

	sort(xs.begin(), xs.end());
	sort(ys.begin(), ys.end());

	xs.erase(unique(xs.begin(), xs.end()), xs.end());
	ys.erase(unique(ys.begin(), ys.end()), ys.end());

	for(int32_t i = 1; i <= n; i++) {
		rects[i].lowerLeftX = lower_bound(xs.begin(), xs.end(), rects[i].lowerLeftX) - xs.begin();
		rects[i].upperRightX = lower_bound(xs.begin(), xs.end(), rects[i].upperRightX) - xs.begin();
		rects[i].lowerLeftY = lower_bound(ys.begin(), ys.end(), rects[i].lowerLeftY) - ys.begin();
		rects[i].upperRightY = lower_bound(ys.begin(), ys.end(), rects[i].upperRightY) - ys.begin();		
	}

	for(int32_t i = 1; i <= m; i++) {
		shots[i].x = lower_bound(xs.begin(), xs.end(), shots[i].x) - xs.begin();
		shots[i].y = lower_bound(ys.begin(), ys.end(), shots[i].y) - ys.begin();
	}

	maxY = ys.size();
}

class SegmentTree {
private:
	int32_t treeSize;
	stack< pair< int32_t, int32_t > > data[4 * (MAX_N + MAX_M)];

	void Build(int32_t node, int32_t low, int32_t high) {
		if(low == high) {
			data[node].push({ 0, 0 });
			return;
		}

		int32_t mid = (low + high) / 2;
		Build(2 * node, low, mid);
		Build(2 * node + 1, mid + 1, high);
	}

	void Update(int32_t node, int32_t low, int32_t high, int32_t qLow, int32_t qHigh, pair< int32_t, int32_t > qVal) {
		if(low > qHigh || high < qLow) {
			return;
		}
		else if(low >= qLow && high <= qHigh) {
			if(qVal.first == -1) {
				data[node].pop();
			}
			else {
				data[node].push(qVal);
			}
			return;
		}

		int32_t mid = (low + high) / 2;
		Update(2 * node, low, mid, qLow, qHigh, qVal);
		Update(2 * node + 1, mid + 1, high, qLow, qHigh, qVal);
	}

	void Query(int32_t node, int32_t low, int32_t high, int32_t qInd, pair< int32_t, int32_t > &ans) {
		if(low > qInd || high < qInd) {
			return;
		}
		
		if(!data[node].empty()) {
			ans = max(ans, data[node].top());
		}
		
		if(low == qInd && high == qInd) {
			return;
		}

		int32_t mid = (low + high) / 2;
		Query(2 * node, low, mid, qInd, ans);
		Query(2 * node + 1, mid + 1, high, qInd, ans);
	}

public:
	void Init(int32_t n) {
		treeSize = n;
		Build(1, 1, treeSize);
	}
	
	void Update(int32_t low, int32_t high, pair< int32_t, int32_t > val) {
		Update(1, 1, treeSize, low, high, val);
	}

	int32_t Query(int32_t ind) {
		pair< int32_t, int32_t > ans = { 0, 0 };
		Query(1, 1, treeSize, ind, ans);
		return ans.second;
	}
};

SegmentTree segTree;

class Event {
public:
	bool isBegining;
	int32_t x, low, high, rectInd;
	
	Event(bool isBegining = false, int32_t x = 0, int32_t low = 0, int32_t high = 0, int32_t rectInd = 0)
		: isBegining(isBegining), x(x), low(low), high(high), rectInd(rectInd) {
		
	}

	bool operator< (const Event &other) {
		if(x != other.x) {
			return x < other.x;
		}
		else if(isBegining != other.isBegining) {
			return isBegining > other.isBegining;
		}
		else {
			return rectInd < other.rectInd;	
		}
	}
};

class Tree {
private:
	class Node {
	public:
		int32_t ans;
		set< int32_t > colors;
		vector< int32_t > v;
	};

	int32_t cntNodes;

public:
	Node nodes[MAX_N];

	void Init(int32_t n) {
		cntNodes = n;
	}

	void AddEdge(int32_t x, int32_t y) {
		nodes[x].v.push_back(y);
	}
	
	void Merge(int32_t x, int32_t y) {
		if(nodes[x].colors.size() < nodes[y].colors.size()) {
			for(int32_t p : nodes[x].colors) {
				nodes[y].colors.insert(p);
			}
			swap(nodes[x].colors, nodes[y].colors);
		}
		else {
			for(int32_t p : nodes[y].colors) {
				nodes[x].colors.insert(p);
			}
		}
	}

	void Dfs(int32_t node) {
		for(int32_t x : nodes[node].v) {
			Dfs(x);	
			if(node != 0) {
				Merge(node, x);
			}
		}
		nodes[node].ans = nodes[node].colors.size();
	}
};

Tree t;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int32_t n, m;
	cin >> n >> m;

	for(int32_t i = 1; i <= n; i++) {
		cin >> rects[i].lowerLeftX >> rects[i].lowerLeftY;
		cin >> rects[i].upperRightX >> rects[i].upperRightY;
		rects[i].ind = i;
	}

	for(int32_t i = 1; i <= m; i++) {
		cin >> shots[i].x >> shots[i].y >> shots[i].color; 
	}

	int32_t maxY;
	Compress(n, m, maxY);

	segTree.Init(maxY);
	
	vector< Event > evs(2 * n + 1);
	for(int32_t i = 1; i <= n; i++) {
		evs[2 * i - 1] = Event(true, rects[i].lowerLeftX, rects[i].lowerLeftY, rects[i].upperRightY, rects[i].ind);
		evs[2 * i] = Event(false, rects[i].upperRightX, rects[i].lowerLeftY, rects[i].upperRightY, rects[i].ind);
	}

	sort(evs.begin() + 1, evs.begin() + 1 + 2 * n);
	
	t.Init(n);
	for(int32_t i = 1; i <= 2 * n; i++) {
		if(evs[i].isBegining) {
			t.AddEdge(segTree.Query(evs[i].low), evs[i].rectInd);
			segTree.Update(evs[i].low, evs[i].high, { i, evs[i].rectInd });
		}
		else {
			segTree.Update(evs[i].low, evs[i].high, { -1, -1 });
		}
	}
	
	for(int32_t i = 1; i <= m; i++) {
		evs.push_back(Event(false, shots[i].x, shots[i].y, i, -1));
	}
	sort(evs.begin() + 1, evs.end());

	for(int32_t i = 1; i < (int32_t) evs.size(); i++) {
		if(evs[i].rectInd == -1) {
			t.nodes[segTree.Query(evs[i].low)].colors.insert(shots[evs[i].high].color);
		}
		else if(evs[i].isBegining) {
			segTree.Update(evs[i].low, evs[i].high, { i, evs[i].rectInd });
		}
		else {
			segTree.Update(evs[i].low, evs[i].high, { -1, -1 });
		}
	}
	
	t.Dfs(0);
	for(int32_t i = 1; i <= n; i++) {
		cout << t.nodes[i].ans << endl;
	}

	return 0;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 442580 KB Output is correct
2 Correct 576 ms 445280 KB Output is correct
3 Correct 393 ms 445280 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 445376 KB Output is correct
2 Correct 627 ms 446792 KB Output is correct
3 Correct 400 ms 446792 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 791 ms 452792 KB Output is correct
2 Correct 796 ms 453320 KB Output is correct
3 Correct 392 ms 453320 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1064 ms 463380 KB Output is correct
2 Correct 1085 ms 464936 KB Output is correct
3 Correct 383 ms 464936 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1050 ms 465564 KB Output is correct
2 Correct 1032 ms 469144 KB Output is correct
3 Correct 393 ms 469144 KB Output is correct