oj.uz

답안 #114243

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114243 2019-05-31T13:57:05 Z Markomafko972 Plahte (COCI17_plahte) C++14
160 / 160
 1798 ms 404716 KB 
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

const int OFF = (1 << 18);

int n, m;
int x[80002];
int y[80002];
int x2[80002];
int y2[80002];
int p1[80002];
int p2[80002];
int b[80002];
vector<int> saz;
vector< pair<int, int> > v[480002];
set<int> s[80002];
set<int> :: iterator it;
int f, w;
int sad = 1;
int koji[80002];
int mset[80002];

vector<int> sus[80002];
stack<int> tour[2*OFF+5];
int maxibr = 0;

void trazi(int l1, int r1, int lo, int hi, int c) {
	//cout << l1 << " " << r1 << " " << lo << " " << hi << " " << c << endl;

	if (hi <= l1 || r1 <= lo) return;
	if (l1 <= lo && hi <= r1) {
		int gdje = c;
		while (gdje > 0) {
			maxibr = max(maxibr, tour[gdje].top());
			gdje /= 2;
		}
		//cout << "da: " << l1 << " " << r1 << " " << lo << " " << hi << endl;
		tour[c].push(koji[w]);
		return;
	} 
	
	trazi(l1, r1, lo, (lo+hi)/2, c*2);
	trazi(l1, r1, (lo+hi)/2, hi, c*2+1);
}

void makni(int l1, int r1, int lo, int hi, int c) {
	if (hi <= l1 || r1 <= lo) return;
	if (l1 <= lo && hi <= r1) {
		tour[c].pop();
		return;
	}
	
	makni(l1, r1, lo, (lo+hi)/2, c*2);
	makni(l1, r1, (lo+hi)/2, hi, c*2+1);
}

void stavi(int l1, int r1, int lo, int hi, int c) {
	if (hi <= l1 || r1 <= lo) return;
	if (l1 <= lo && hi <= r1) {
		int gdje = c;
		
		//cout << l1 << " " << r1 << " " << lo << " " << hi << endl;
		while (gdje > 0) {
			s[tour[gdje].top()].insert(b[w]);
			//cout << tour[gdje].top() << endl;
			gdje /= 2;
		}
		
		return;
	}
	
	stavi(l1, r1, lo, (lo+hi)/2, c*2);
	stavi(l1, r1, (lo+hi)/2, hi, c*2+1);
}

int rj[80002];

void rek(int tren) {
	
	if (tren == 0) {
		for (int i = 0; i < sus[0].size(); i ++) {
			rek(sus[0][i]);
		}
		
		return;
	}
	
	if (sus[tren].size() == 0) {
		rj[tren] = s[ mset[tren] ].size();
		return;
	}
	
	for (int i = 0; i < sus[tren].size(); i ++) {
		rek(sus[tren][i]);
	}
	
	int najv = 0, ind = 0;
	for (int i = 0; i < sus[tren].size(); i ++) {
		int slj = sus[tren][i];
		if (s[ mset[slj] ].size() > najv) {
			najv = s[ mset[slj] ].size();
			ind = i;
		}
	}
	
	for (it = s[ mset[tren] ].begin(); it != s[ mset[tren] ].end(); it ++) {
		s[ mset[ sus[tren][ind] ] ].insert(*it);	
	}
	
	mset[tren] = mset[ sus[tren][ind] ];
	for (int i = 0; i < sus[tren].size(); i ++) {
		if (i != ind) {
			int slj = sus[tren][i];
			for (it = s[ mset[slj] ].begin(); it != s[ mset[slj] ].end(); it ++) {
				s[ mset[tren] ].insert(*it);
			}
		}
	}
	
	rj[tren] = s[ mset[tren] ].size();
}

int main () {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i ++) {
		cin >> x[i] >> y[i] >> x2[i] >> y2[i];
		saz.push_back(x[i]);
		//saz.push_back(y[i]);
		saz.push_back(x2[i]);
		//saz.push_back(y2[i]);
	}
	
	for (int i = 0; i < m; i ++) {
		cin >> p1[i] >> p2[i] >> b[i];
		saz.push_back(p1[i]);
		//saz.push_back(p2[i]);
	}
	
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());
	for (int i = 0; i < n; i ++) {
		x[i] = lower_bound(saz.begin(), saz.end(), x[i]) - saz.begin();
		//y[i] = lower_bound(saz.begin(), saz.end(), y[i]) - saz.begin();
		x2[i] = lower_bound(saz.begin(), saz.end(), x2[i]) - saz.begin();
		//y2[i] = lower_bound(saz.begin(), saz.end(), y2[i]) - saz.begin();
		
		//cout << "(" << x[i] << "," << y[i] << ") -> (" << x2[i] << "," << y2[i] << ")" << endl; 
		
		v[x[i]].push_back({-1, i});
		v[x2[i]].push_back({1, i});
	}
	
	for (int i = 0; i < m; i ++) {
		p1[i] = lower_bound(saz.begin(), saz.end(), p1[i]) - saz.begin();
		//p2[i] = lower_bound(saz.begin(), saz.end(), p2[i]) - saz.begin();
		
		//cout << "(" << p1[i] << "," << p2[i] << ")" << endl;
	
		v[p1[i]].push_back({0, i});
	}
	
	saz.clear();
	for (int i = 0; i < n; i ++) {
		//saz.push_back(x[i]);
		saz.push_back(y[i]);
		//saz.push_back(x2[i]);
		saz.push_back(y2[i]);
	}
	for (int i = 0; i < m; i ++) {
		//saz.push_back(p1[i]);
		saz.push_back(p2[i]);
	}
	
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());
	for (int i = 0; i < n; i ++) {
		//x[i] = lower_bound(saz.begin(), saz.end(), x[i]) - saz.begin();
		y[i] = lower_bound(saz.begin(), saz.end(), y[i]) - saz.begin();
		//x2[i] = lower_bound(saz.begin(), saz.end(), x2[i]) - saz.begin();
		y2[i] = lower_bound(saz.begin(), saz.end(), y2[i]) - saz.begin();
	}
	
	for (int i = 0; i < m; i ++) {
		//p1[i] = lower_bound(saz.begin(), saz.end(), p1[i]) - saz.begin();
		p2[i] = lower_bound(saz.begin(), saz.end(), p2[i]) - saz.begin();
	}
	
	saz.clear();
	for (int i = 0; i < m; i ++) {
		saz.push_back(b[i]);
	}
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());
	for (int i = 0; i < m; i ++) {
		b[i] = lower_bound(saz.begin(), saz.end(), b[i]) - saz.begin();
	}
	
	for (int i = 0; i <= 2*OFF; i ++) tour[i].push(0);
	
	for (int i = 0; i <= 480000; i ++) {
		sort(v[i].begin(), v[i].end());
		for (int j = 0; j < v[i].size(); j ++) {
			f = v[i][j].X;
			w = v[i][j].Y;
			if (f == -1) koji[w] = sad, sad ++;
			
			if (f == -1) {
				maxibr = 0;
				trazi(y[w], y2[w]+1, 0, OFF, 1);
				sus[maxibr].push_back(koji[w]);
			}
			else if (f == 0) {
				//cout << "DA!" << endl;
				stavi(p2[w], p2[w]+1, 0, OFF, 1);
			}
			else {
				makni(y[w], y2[w]+1, 0, OFF, 1);
			}
			
			//cout << f << ": " << w << endl;
			/*int pr = 2;
			for (int k = 1; k < OFF*2; k ++) {
				if (k == pr) {
					cout << endl;
					pr *= 2;
				}
				cout << tour[k].top() << " ";
			}
			cout << endl;*/
		}
	}
	
	for (int i = 1; i < sad; i ++) mset[i] = i;
	rek(0);
	
	/*for (int i = 0; i <= n; i ++) {
		cout << i << ": ";
		for (int j = 0; j < sus[i].size(); j ++) cout << sus[i][j] << " ";
		cout << endl;
	}*/
	
	for (int i = 1; i <= n; i ++) {
		//cout << "KOJI: " << koji[i] << endl;
		//cout << p[koji[i-1]].count() << endl;
		cout << rj[ koji[i-1] ] << endl;
	}
	
	return 0;
}

Compilation message

plahte.cpp: In function 'void rek(int)':
plahte.cpp:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < sus[0].size(); i ++) {
                   ~~^~~~~~~~~~~~~~~
plahte.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < sus[tren].size(); i ++) {
                  ~~^~~~~~~~~~~~~~~~~~
plahte.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < sus[tren].size(); i ++) {
                  ~~^~~~~~~~~~~~~~~~~~
plahte.cpp:102:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (s[ mset[slj] ].size() > najv) {
       ~~~~~~~~~~~~~~~~~~~~~~^~~~~~
plahte.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < sus[tren].size(); i ++) {
                  ~~^~~~~~~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:207:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v[i].size(); j ++) {
                   ~~^~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 708 ms 380428 KB Output is correct
2 Correct 709 ms 380496 KB Output is correct
3 Correct 422 ms 370328 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 777 ms 382832 KB Output is correct
2 Correct 802 ms 381532 KB Output is correct
3 Correct 468 ms 370296 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1113 ms 392180 KB Output is correct
2 Correct 1036 ms 390144 KB Output is correct
3 Correct 411 ms 370240 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1678 ms 403596 KB Output is correct
2 Correct 1520 ms 404716 KB Output is correct
3 Correct 408 ms 370392 KB Output is correct

Subtask #5
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1798 ms 403612 KB Output is correct
2 Correct 1458 ms 400236 KB Output is correct
3 Correct 403 ms 370300 KB Output is correct