oj.uz

답안 #159459

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
159459 2019-10-22T19:40:42 Z Atalasion Plahte (COCI17_plahte) C++14
0 / 160
 560 ms 187056 KB 
//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], lazy[N << 3];
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) continue;
		if (u == ind) DFS(u, v, 1);
		else DFS(u, v, 0);
	}
	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);
	}
	if (f == 0){
		for (auto u:sub_t[v]){
			cnt[col[u]] --;
		}
	}
	return;
}

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

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];
		Px.pb(poi[i].F), Py.pb(poi[i].S);
	}
	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});
	}
	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));
			COL[dad].pb(u.S);
		}
		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 <= m; i++){
		G[par[i]].pb(i);
		G[i].pb(par[i]);
	}
	solve();
	for (int i = 1; i <= n; i++) cout << ans[i] << '\n';




	return 0;
}

Compilation message

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:138: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:139: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
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 236 ms 70600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 239 ms 73704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 390 ms 159464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 539 ms 186472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 560 ms 187056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -