oj.uz

답안 #44352

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
44352 2018-03-31T16:25:27 Z JustInCase Plahte (COCI17_plahte) C++17
0 / 160
 2000 ms 524288 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;

	bool operator< (const Rectangle &x) const {
		if(lowerLeftX != x.lowerLeftX) {
			return lowerLeftX < x.lowerLeftX;
		}
		else {
			return upperRightY < x.upperRightY;
		}
	}
};

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 {
			return isBegining > other.isBegining;
		}
	}
};

class Tree {
private:
	class Node {
	public:
		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()) {
			set< int32_t > ansSet = nodes[y].colors;
			for(int32_t p : nodes[x].colors) {
				ansSet.insert(p);
			}
			nodes[x].colors = ansSet;
		}
		else {
			set< int32_t > ansSet = nodes[x].colors;
			for(int32_t p : nodes[y].colors) {
				ansSet.insert(p);
			}
			nodes[x].colors = ansSet;
		}
	}

	void Dfs(int32_t node) {
		for(int32_t x : nodes[node].v) {
			Dfs(x);	
			Merge(node, x);
		}
	}
};

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; 
	}

	sort(rects + 1, rects + 1 + n);
	
	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].lowerLeftX, rects[i].upperRightY, rects[i].ind);
		evs[2 * i] = Event(false, rects[i].upperRightX, rects[i].lowerLeftY, rects[i].upperRightX, 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(true, shots[i].x, shots[i].y, i, -1));
	}
	sort(evs.begin() + 1, evs.end());

	for(int32_t i = 1; i < 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].colors.size() << endl;
	}

	return 0;
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:256:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int32_t i = 1; i < evs.size(); i++) {
                     ~~^~~~~~~~~~~~

Subtask #1
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2094 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2057 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2172 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2084 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2092 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -