제출 #159472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159472		Atalasion	Plahte (COCI17_plahte)	C++14	160 / 160	639 ms	110448 KiB

plahte

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimise ("ofast")
#pragma GCC optimise("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 160000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;

int n, m, col[N], par[N];
ll lazy[N << 4];
vi COL[N];
pair<pii, pii> rect[N];
pii poi[N];
vector<int> Px, Py;
vector<pair<pii, int>> vl[N << 2], vr[N << 2];
vector<pii> Ge[N << 2]; 
unordered_map<int, int> kojx, kojy;

void modify(int id, ll x){
	lazy[id] += x;
	return;
}

void shift(int id){
	modify(id << 1, lazy[id]);
	modify(id << 1 | 1, lazy[id]);
	lazy[id] = 0;
	return;
}

void add(int id, int lq, int rq, int x, int l, int r){
	if (rq <= l || r <= lq) return;
	if (lq <= l && r <= rq){
		modify(id, x);
		return;
	}
	int mid = (l + r) >> 1;
	shift(id);
	add(id << 1, lq, rq, x, l, mid);
	add(id << 1 | 1, lq, rq, x, mid, r);
	//seg[id] = seg[id << 1] + seg[id << 1 | 1];
	return;
}

ll get(int id, int lq, int rq, int l, int r){
	if (rq <= l || r <= lq) return 0;
	if (lq <= l && r <= rq){
		return lazy[id];
	}
	shift(id);
	int mid = (l + r) >> 1;
	return get(id << 1, lq, rq, l, mid) + get(id << 1 | 1, lq, rq, mid, r);
}

vi G[N], sub_t[N];
int child[N], cnt[N], ans[N];

void DFS_c(int v = 0, int p = 0){
	child[v] += COL[v].size();
	for (auto u:G[v]){
		if (u == p) continue;
		DFS_c(u, v);
		child[v] += child[u];
	}
	return;
}

void DFS(int v = 0, int p = 0, bool f = 1){
	int Mx = -1, ind = N - 1;
	for (auto u:G[v]){
		if (u == p) continue;
		if (Mx < child[u]) Mx = child[u], ind = u;
	}
	for (auto u:G[v]){
		if (u == p || u == ind) continue;
		DFS(u, v, 0);
	}
	if (ind != N - 1) DFS(ind, v, 1);
	ans[v] = ans[ind];
	sub_t[v].swap(sub_t[ind]);
	for (auto u:G[v]){
		if (u == p || u == ind) continue;
		for (auto x:sub_t[u]){
			cnt[col[x]] ++;
			sub_t[v].pb(x);
			if (cnt[col[x]] == 1) ans[v]++;
		}
		sub_t[u].shrink_to_fit();
	}
	for (auto u:COL[v]){
		cnt[col[u]]++;
		if (cnt[col[u]] == 1) ans[v]++;
		sub_t[v].pb(u);
	}
//	cout << v << '\n';
//	for (int i = 1; i <= 3; i++) cout << cnt[i] << ' ';
//	cout << '\n';
	if (f == 0){
		for (auto u:sub_t[v]){
			cnt[col[u]] --;
		}
	}
	return;
}

void solve(){
	DFS_c(0);
	DFS();
	return;
}

vector<int> CC;
map<int, int> kojC;
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		rect[i] = {{x1, y1}, {x2, y2}};
		Px.pb(x1), Px.pb(x2), Py.pb(y1), Py.pb(y2);
	}
	for (int i = 1; i <= m; i++){
		cin >> poi[i].F >> poi[i].S >> col[i];
		CC.pb(col[i]);
		Px.pb(poi[i].F), Py.pb(poi[i].S);
	}
	sort(all(CC));
	CC.resize(unique(all(CC)) - CC.begin());
	for (int i = 0; i < CC.size(); i++){
		kojC[CC[i]] = i + 1;
	}
	for (int i = 1; i <= m; i++){
		col[i] = kojC[col[i]];
	}
	sort(all(Px));
	sort(all(Py));
	Px.resize(unique(all(Px)) - Px.begin());
	Py.resize(unique(all(Py)) - Py.begin());
	for (int i = 0; i < Px.size(); i++) kojx[Px[i]] = i + 1;
	for (int i = 0; i < Py.size(); i++) kojy[Py[i]] = i + 1;
	for (int i = 1; i <= n; i++){
		vl[kojx[rect[i].F.F]].pb({{kojy[rect[i].F.S], kojy[rect[i].S.S]}, i});
		vr[kojx[rect[i].S.F]].pb({{kojy[rect[i].F.S], kojy[rect[i].S.S]}, i});
	}
	for (int i = 1; i <= m; i++){
		Ge[kojx[poi[i].F]].pb({kojy[poi[i].S], i});
	}
	//return 0;
	for (int i = 1; i < (N << 2); i++){
		for (auto u:vl[i]){
			//cout << u.S << '\n';
			//cout << u.F.F << ' ' << u.F.S << '\n';
			par[u.S] = get(1, u.F.F, u.F.F + 1, 1, (N << 2));
			add(1, u.F.F, u.F.S + 1, u.S - par[u.S], 1, (N << 2));
		}
		for (auto u:Ge[i]){
			ll dad = get(1, u.F, u.F + 1, 1, (N << 2));
		//	if (u.S == 1) dad = 1;
			COL[dad].pb(u.S);
			//cout << u.S << ' ' << dad << '\n';
		}
		for (auto u:vr[i]){
			add(1, u.F.F, u.F.S + 1, par[u.S] - u.S, 1, (N << 2));
		}
		vl[i].shrink_to_fit();
		vr[i].shrink_to_fit();
		Ge[i].shrink_to_fit();
	}
	//for (int i = 1; i <= n; i++) cout << par[i] << ' ';
	for (int i = 1; i <= n; i++){
		G[par[i]].pb(i);
		G[i].pb(par[i]);
	}
	//cout << '\n';
	//return 0;
	solve();
	for (int i = 1; i <= n; i++) cout << ans[i] << '\n';




	return 0;
}

/*
5 3
1 1 11 10
2 7 7 9
6 2 9 6
7 4 8 5
3 2 5 4
4 6 1
6 8 3
8 5 2
*/

컴파일 시 표준 에러 (stderr) 메시지

plahte.cpp:8:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise ("ofast")
 
plahte.cpp:9:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise("unroll-loops")
 
plahte.cpp: In function 'int main()':
plahte.cpp:143:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < CC.size(); i++){
                  ~~^~~~~~~~~~~
plahte.cpp:153:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Px.size(); i++) kojx[Px[i]] = i + 1;
                  ~~^~~~~~~~~~~
plahte.cpp:154:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Py.size(); i++) kojy[Py[i]] = i + 1;
                  ~~^~~~~~~~~~~

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