제출 #1129624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129624		idiotcomputer	Plahte (COCI17_plahte)	C++17	160 / 160	466 ms	131984 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second 
#define ll long long int 
#define pb push_back
#define sz(x) (int) (x).size()

const int mxN = 8e4;
const int mxM = 8e4;
const int inf = 1e9+5;
int n,m;

pii rect[mxN][2];
pii points[mxM];
int col[mxM];
int par[mxN];
int tot[mxN];

int p[mxN];
unordered_map<int,bool> vals[mxN];

int getp(int a){
	if (p[a] == a) return a;
	p[a] = getp(p[a]);
	return p[a];
}

void join(int a, int b){
//	cout << "JOINING " << a << " " << b << '\n';
//	for(int i = 0; i < n; i++) cout << p[i] << " ";
//	cout << '\n';
	//return;
	if (a == -1 || b == -1) return;
	a = getp(a);
	b = getp(b);
	
	//	if (a == -1 || b == -1) return;

//	if (a == 0 && b == 2) return;
	if (sz(vals[a]) < sz(vals[b])) swap(a,b);

	for (pii c : vals[b]) vals[a][c.f] = 1;
	vals[b].clear();
	//cout << a << " " << b << '\n';
	p[b] = a;
}

using sn = struct node*;
struct node {
	int l,r;
	vector<pii> v;
	sn c[2] = {nullptr,nullptr};
	node(int tl, int tr) {
		l = tl;
		r = tr;
	}
};

void add(sn cur, int tl, int tr, pii v){
	int l = cur->l;
	int r = cur->r;
	if (l > tr || r < tl) return;
	if (l >= tl & r <= tr){
		cur->v.pb(v);
		return;
	}
	int m = (l+r)/2;
	if (cur->c[0] == nullptr) cur->c[0] = new node(l,m);
	if (cur->c[1] == nullptr) cur->c[1] = new node(m+1,r);
	add(cur->c[0],tl,tr,v);
	add(cur->c[1],tl,tr,v);
}

void sub(sn cur, int tl, int tr){
	int l = cur->l;
	int r = cur->r;
	if (l > tr || r < tl) return;
	if (l >= tl & r <= tr){
		cur->v.pop_back();
		return;
	}
	int m = (l+r)/2;
	if (cur->c[0] != nullptr) sub(cur->c[0],tl,tr);
	if (cur->c[1] != nullptr) sub(cur->c[1],tl,tr);
}

void comb(pii a, pii &b){
	//combine a into b
	if (b.f > a.f) b = a;
}

pii query(sn cur, int tl, int tr){
	int l = cur->l;
	int r = cur->r;
	

	pii res = {inf,-1};
	if (l > tr || r < tl) return res;
	if (sz(cur->v)) res = cur->v.back();
	if (l >= tl && r <= tr) return res;

	if (cur->c[0] != nullptr) comb(query(cur->c[0],tl,tr),res);
	if (cur->c[1] != nullptr) comb(query(cur->c[1],tl,tr),res);
	return res;
}


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

	cin >> n >> m;
	vector<pii> all;
	for (int i = 0; i < n; i++){
		cin >> rect[i][0].f >> rect[i][0].s >> rect[i][1].f >> rect[i][1].s;
		all.pb({rect[i][0].f, i});
		all.pb({rect[i][1].f, n+m+i});
	}

	for (int i = 0; i < m; i++){
		cin >> points[i].f >> points[i].s >> col[i];
		all.pb({points[i].f,n+i});
	}

	sort(all.begin(),all.end());
	sn root = new node(0,1e9);
	for (int i = 0; i < n; i++) p[i] = i;
	for (int i = 0; i < sz(all); i++){
		if (all[i].s < n){
			// start of rect
			int y1 = rect[all[i].s][0].s;
			int y2 = rect[all[i].s][1].s;
		///	cout << "ADDING " << y1 << "," << y2 << '\n';
			pii c = query(root,y1,y2);
			par[all[i].s] = c.s;
			add(root,y1,y2,{y2-y1,all[i].s});
		} else if (all[i].s >= n+m){
			//end of rect
			//continue;
			int y1 = rect[all[i].s-n-m][0].s;
			int y2 = rect[all[i].s-n-m][1].s;
			tot[all[i].s-n-m] = sz(vals[getp(all[i].s-n-m)]);
			join(all[i].s-n-m,par[all[i].s-n-m]);
			sub(root,y1,y2);
		} else {
			//point
			int y = points[all[i].s-n].s;
			int idx = query(root,y,y).s;
			///cout << y<< " - " << idx << '\n';
			if (idx == -1) continue;
			idx = getp(idx);
			vals[idx][col[all[i].s-n]] = 1;
		}
	}
//	for (int i = 0; i < n; i++) cout << par[i] << " ";
//	cout << '\n';
	for (int i = 0; i < n; i++) cout << tot[i] << "\n";
	return 0;
}

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32