Submission #79848

#	Time	Username	Problem	Language	Result	Execution time	Memory
79848		pzdba	Plahte (COCI17_plahte)	C++14	160 / 160	471 ms	50980 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
vector<int> g[80005];
vector<int> h1, h2;
int par[80005];
int deg[80005];
pii p[80005];
int a[80005], b[80005], c[80005], d[80005];
int x[80005], y[80005], k[80005];
vector<int> o1[240005], o2[240005], o3[240005];
set<int> sz[80005];
set<int>::iterator its;
int ans[80005];
void dfs(int u){
	for(int i=0;i<g[u].size();i++){
		int v = g[u][i];
		dfs(v);
		if(sz[v].size() > sz[u].size()) swap(sz[u], sz[v]);
		for(its = sz[v].begin(); its != sz[v].end();its++) sz[u].insert(*its);
	}
	ans[u] = sz[u].size();
}
int main(){
	memset(par, -1, sizeof(par));
	int n, m;
	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]);
		h1.emplace_back(a[i]);
		h1.emplace_back(c[i]);
		h2.emplace_back(b[i]);
		h2.emplace_back(d[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d", &x[i], &y[i], &k[i]);
		h1.emplace_back(x[i]);
		h2.emplace_back(y[i]);
	}
	sort(h1.begin(), h1.end());
	sort(h2.begin(), h2.end());
	h1.erase(unique(h1.begin(), h1.end()), h1.end());
	h2.erase(unique(h2.begin(), h2.end()), h2.end());
	for(int i=1;i<=n;i++){
		a[i] = lower_bound(h1.begin(), h1.end(), a[i]) - h1.begin() + 1;
		c[i] = lower_bound(h1.begin(), h1.end(), c[i]) - h1.begin() + 1;

		b[i] = lower_bound(h2.begin(), h2.end(), b[i]) - h2.begin() + 1;
		d[i] = lower_bound(h2.begin(), h2.end(), d[i]) - h2.begin() + 1;
	}
	for(int i=1;i<=m;i++){
		x[i] = lower_bound(h1.begin(), h1.end(), x[i]) - h1.begin() + 1;
		y[i] = lower_bound(h2.begin(), h2.end(), y[i]) - h2.begin() + 1;
	}
	set<pii> sweep;
	set<pii>::iterator its;
	for(int i=1;i<=n;i++){
		o1[a[i]].emplace_back(i);
		o2[c[i]].emplace_back(i);
	}
	for(int i=1;i<=m;i++){
		o3[x[i]].emplace_back(i);
	}
	for(int i=1;i<=240000;i++){
		for(int j=0;j<o1[i].size();j++){
			int idx = o1[i][j];
			its = sweep.upper_bound(pii(b[idx], 2e9));
			if(its != sweep.begin()) its--;
			if(its != sweep.end()){
				int u = its->second;
				if(!(b[u] <= b[idx] && d[idx] <= d[u])) u = par[u];
				if(u == -1 || !(b[u] <= b[idx] && b[idx] <= d[u])) u = -1;
				if(u != -1){
					g[u].emplace_back(idx);
					par[idx] = u;
					deg[idx]++;
				}
			}
		}
		for(int j=0;j<o1[i].size();j++){
			int idx = o1[i][j];
			sweep.insert(pii(b[idx], idx));
			sweep.insert(pii(d[idx], idx));
		}
		for(int j=0;j<o3[i].size();j++){
			int idx = o3[i][j];
			its = sweep.upper_bound(pii(y[idx], 2e9));
			if(its != sweep.begin()) its--;
			if(its != sweep.end()){
				int u = its->second;
				if(!(b[u] <= y[idx] && y[idx] <= d[u])) u = par[u];
				if(u == -1 || !(b[u] <= y[idx] && y[idx] <= d[u])) u = -1;
				if(u != -1){
					sz[u].insert(k[idx]);
				}
			}
		}
		for(int j=0;j<o2[i].size();j++){
			int idx = o2[i][j];
			sweep.erase(sweep.find(pii(b[idx], idx)));
			sweep.erase(sweep.find(pii(d[idx], idx)));
		}
	}
	for(int i=1;i<=n;i++){
		if(deg[i] == 0) dfs(i);
	}
	for(int i=1;i<=n;i++) printf("%d\n", ans[i]);

}

Compilation message (stderr)

plahte.cpp: In function 'void dfs(int)':
plahte.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[u].size();i++){
              ~^~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<o1[i].size();j++){
               ~^~~~~~~~~~~~~
plahte.cpp:80:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<o1[i].size();j++){
               ~^~~~~~~~~~~~~
plahte.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<o3[i].size();j++){
               ~^~~~~~~~~~~~~
plahte.cpp:98:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<o2[i].size();j++){
               ~^~~~~~~~~~~~~
plahte.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
plahte.cpp:29:8: 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:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x[i], &y[i], &k[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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