oj.uz

Submission #199040

# Submission time Handle Problem Language Result Execution time Memory
199040 2020-01-28T18:15:17 Z ZwariowanyMarcin Plahte (COCI17_plahte) C++14
160 / 160
 340 ms 32988 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define LL long long
#define ld long double
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define boost cin.tie(0), ios_base::sync_with_stdio(0);


using namespace std;		

const int nax = 80111;
const int pod = (1 << 18);

int n, m;
int a[nax], b[nax], c[nax], d[nax];
int e[nax], f[nax], col[nax];
int par[nax];

struct pro {
	int x, l, r, id, type, dod;
};

vector <pro> v;

vector <int> val;

vector <int> gao[nax];

vector <int> g[nax];

int daj(int x) {
	return (int) (lower_bound(val.begin(), val.end(), x) - val.begin());
}

struct seg {
	pair <int, int> t[2 * pod];
	
	void init() {
		for (int i = 1; i < 2 * pod; ++i)
			t[i] = {0, 0};
	}
	
	void ustaw(int l, int r, int k, int czas) {
		r++;
		for (l += pod, r += pod; l < r; l /= 2, r /= 2) {
			if (l & 1) t[l++] = {czas, k};
			if (r & 1) t[--r] = {czas, k};
		}
	}
	
	int query(int x) {
		pair <int, int> best = {-1, -1};
		x += pod;
		while (x) {
			best = max(best, t[x]);
			x /= 2;
		}
		return best.se;
	}
} ja;

set <int> *se[nax];

int ans[nax];

void dfs(int u, int p) {
	pair <int, int> big = {-1, -1};
	for (auto it : g[u]) {
		dfs(it, u);
		big = max(big, {se[it]->size(), it});
	}
	if (big.fi == -1) {
		se[u] = new set <int> ();
	}
	else {
		se[u] = se[big.se];
	}
	
	for (auto it : g[u])
		if (it != big.se)
			for (auto it : *se[it])
				se[u]->insert(it);
	for (auto it : gao[u])
		se[u]->insert(it);
	ans[u] = se[u]->size();
}

int main() {	
	ja.init();
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf ("%d%d%d%d", a + i, b + i, c + i, d + i);
		val.pb(b[i]);
		val.pb(d[i]);
	}
	
	for (int i = 1; i <= m; ++i) {
		scanf ("%d%d%d", e + i, f + i, col + i);
		val.pb(f[i]);
	}
	
	sort(val.begin(), val.end());
	val.erase(unique(val.begin(), val.end()), val.end());
		
	for (int i = 1; i <= n; ++i) {
		v.pb({a[i], daj(b[i]), daj(d[i]), i, 0, 1});
		v.pb({c[i], daj(b[i]), daj(d[i]), i, 0, -1});
	}
	
	for (int i = 1; i <= m; ++i) 
		v.pb({e[i], daj(f[i]), daj(f[i]), i, 1, 0});
		
	sort(v.begin(), v.end(), [](pro a, pro b) {
		if (a.x != b.x) return a.x < b.x;
		if (a.type == b.type) return a.dod > b.dod;
		if (a.dod == -1 || b.dod == -1) return a.type > b.type;
		return a.type < b.type;
	});
	
	int CZAS = 0;
	
	for (auto it : v) {
		CZAS++;
		if (it.type == 1) {
			int kto = ja.query(it.l);
			gao[kto].pb(col[it.id]);
		}
		else {
			if (it.dod == 1) {
				par[it.id] = ja.query(it.l);
				ja.ustaw(it.l, it.r, it.id, CZAS);
			}
			else {
				ja.ustaw(it.l, it.r, par[it.id], CZAS);
			}
		}
	}
	
	for (int i = 1; i <= n; ++i) 
		g[par[i]].pb(i);
		
	dfs(0, 0);
	
	for (int i = 1; i <= n; ++i)
		printf ("%d\n", ans[i]);
	
	return 0;
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &m);
  ~~~~~~^~~~~~~~~~~~~~~~
plahte.cpp:97:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d%d%d", a + i, b + i, c + i, d + i);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d%d", e + i, f + i, col + i);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 15204 KB Output is correct
2 Correct 105 ms 16168 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 16988 KB Output is correct
2 Correct 121 ms 16856 KB Output is correct
3 Correct 10 ms 8312 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 23696 KB Output is correct
2 Correct 203 ms 22380 KB Output is correct
3 Correct 12 ms 8184 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 32988 KB Output is correct
2 Correct 340 ms 29524 KB Output is correct
3 Correct 10 ms 8312 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 31556 KB Output is correct
2 Correct 340 ms 31068 KB Output is correct
3 Correct 11 ms 8316 KB Output is correct