oj.uz

Submission #159652

# Submission time Handle Problem Language Result Execution time Memory
159652 2019-10-23T18:02:29 Z ruler Plahte (COCI17_plahte) C++14
96 / 160
 269 ms 59264 KB 
// IOI 2021
 
#include <bits/stdc++.h>
using namespace std;

#define sync ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
#define debug(x) cerr << #x << ": " << x << endl
#define debugP(p) cerr << #p << ": {" << p.first << ", " << p.second << '}' << endl
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e9, MOD = INF + 7;
 
/////////////////////////////////////////////////////////////////////
 
const int N = 2e5 + 5;

struct Point { int x = 0, y = 0, c = 0; };
struct Rect { Point l, r; };

Rect sheets[N];
Point shots[N];
vector< pair<pii, int> > swpL[N], swpR[N];
vector<pii> swpD[N];
int seg[4 * N], par[N], st[N], fn[N], ver[N], cnt[N], ans[N], sz[N], ts, tot;
vector<int> cols[N], g[N];

int get(int p, int id = 1, int s = 0, int e = N) {
	if (e - s < 2) return seg[id];
	int md = (s + e) / 2;
	if (p < md) return seg[id] + get(p, 2 * id, s, md);
	else return seg[id] + get(p, 2 * id + 1, md, e);
}
void update(int l, int r, int val, int id = 1, int s = 0, int e = N) {
	if (l <= s && e <= r) {
		seg[id] += val;
		return;
	}
	if (l >= e || s >= r) return;
	int md = (s + e) / 2;
	update(l, r, val, 2 * id, s, md);
	update(l, r, val, 2 * id + 1, md, e);
}
void add(int c) { if (cnt[c]++ == 0) tot++; }
void del(int c) { if (--cnt[c] == 0) tot--; }
int pre(int v = 0) {
	st[v] = ts++, ver[st[v]] = v;
	sz[v] += sz(cols[v]);
	for (int u : g[v]) sz[v] += pre(u);
	fn[v] = ts;
	return sz[v];
}
void dfs(int v = 0, bool keep = 0) {
	int big = -1;
	for (int u : g[v]) if (big == -1 || sz[big] < sz[u]) big = u;
	for (int u : g[v]) if (u != big) dfs(u, 0);
	if (big != -1) dfs(big, 1);
	for (int u : g[v]) if (u != big) {
		for (int t = st[u]; t < fn[u]; t++) {
			int w = ver[t];
			for (int c : cols[w]) add(c);
		}
	}
	for (int c : cols[v]) add(c);
	ans[v] = tot;
	if (!keep) {
		for (int t = st[v]; t < fn[v]; t++) {
			int w = ver[t];
			for (int c : cols[w]) del(c);
		}	
	}
}

int main() {
 
	sync;

	int n, m; cin >> n >> m;
	vector<int> compX, compY, compC;
	for (int i = 1; i <= n; i++) {
		Rect &rec = sheets[i];
		cin >> rec.l.x >> rec.l.y >> rec.r.x >> rec.r.y;
		compX.push_back(rec.l.x);
		compX.push_back(rec.r.x);
		compY.push_back(rec.l.y);
		compY.push_back(rec.r.y);
	}
	for (int i = 1; i <= m; i++) {
		Point &poi = shots[i];
		cin >> poi.x >> poi.y >> poi.c;
		compX.push_back(poi.x);
		compY.push_back(poi.y);
		compC.push_back(poi.c);
	}
	sort(all(compX)); compX.resize(unique(all(compX)) - compX.begin());
	sort(all(compY)); compY.resize(unique(all(compY)) - compY.begin());
	sort(all(compC)); compC.resize(unique(all(compC)) - compC.begin());
	for (int i = 1; i <= n; i++) {
		Rect &rec = sheets[i];
		rec.l.x = lower_bound(all(compX), rec.l.x) - compX.begin() + 1;
		rec.l.y = lower_bound(all(compY), rec.l.y) - compY.begin() + 1;
		rec.r.x = lower_bound(all(compX), rec.r.x) - compX.begin() + 1;
		rec.r.y = lower_bound(all(compY), rec.r.y) - compY.begin() + 1;
		swpL[rec.l.x].push_back(make_pair(make_pair(rec.l.y, rec.r.y), i));
		swpR[rec.r.x].push_back(make_pair(make_pair(rec.l.y, rec.r.y), i));

	}
	for (int i = 1; i <= m; i++) {	
		Point &poi = shots[i];
		poi.x = lower_bound(all(compX), poi.x) - compX.begin() + 1;
		poi.y = lower_bound(all(compY), poi.y) - compY.begin() + 1;
		swpD[poi.x].push_back(make_pair(poi.y, i));
	}
	for (int i = 1; i < N; i++) {
		for (auto d : swpL[i]) {
			par[d.second] = get(d.first.first);
			update(d.first.first, d.first.second + 1, d.second - par[d.second]);
		}
		for (auto d : swpD[i]) {
			int p = get(d.first);
			cols[p].push_back(shots[d.second].c);
		}
		for (auto d : swpR[i]) {
			update(d.first.first, d.first.second + 1, - d.second + par[d.second]);
		}
	}
	for (int i = 1; i <= n; i++) g[par[i]].push_back(i);
	pre();
	dfs();
	for (int i = 1; i <= n; i++) cout << ans[i] << endl;

  	return 0;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 30188 KB Output is correct
2 Correct 135 ms 31468 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 32616 KB Output is correct
2 Correct 159 ms 33436 KB Output is correct
3 Correct 25 ms 23928 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 38960 KB Output is correct
2 Correct 269 ms 39012 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 190 ms 59232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 192 ms 59264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -