oj.uz

Submission #42323

# Submission time Handle Problem Language Result Execution time Memory
42323 2018-02-26T05:28:03 Z milmillin Plahte (COCI17_plahte) C++14
160 / 160
 518 ms 74448 KB 
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

int a[100100];
int b[100100];
int c[100100];
int d[100100];
int x[100100];
int y[100100];
int k[100100];

const int size = (1<<18);

struct node {
	int ord,idx;
};

struct tree {
	vector<node> nodes[size*2];
	
	void add(int idx,int l,int r,int ll,int rr, node nd) {
		if (rr<=l||ll>=r) return;
		if (ll<=l&&rr>=r) {
			nodes[idx].push_back(nd);
			return;
		}
		int m = (l+r)>>1;
		add(idx*2,l,m,ll,rr,nd);
		add(idx*2+1,m,r,ll,rr,nd);
	}	

	void rem(int idx,int l,int r,int ll,int rr) {
		if (rr<=l||ll>=r) return;
		if (ll<=l&&rr>=r) {
			nodes[idx].pop_back();
			return;
		}
		int m = (l+r)>>1;
		rem(idx*2,l,m,ll,rr);
		rem(idx*2+1,m,r,ll,rr);
	}
	
	int get(int pos) {
		pos+=size;

		int last=-1;
		int ret=-1;

		while (pos) {
			if (!nodes[pos].empty()&&nodes[pos].back().ord>last) {
				last=nodes[pos].back().ord;
				ret = nodes[pos].back().idx;
			}
			pos/=2;
		}
		return ret;
	}
} T;

struct event {
	int x;
	int p;
	int y1;
	int y2;
};

bool operator< (const event &a, const event &b) {
	if (a.x!=b.x) return a.x<b.x;
	if (a.p!=b.p) return a.p<b.p;
	if (a.y1!=b.y1) return a.y1<b.y1;
	return a.y2<b.y2;
}

set<int> cols[100100];
vector<int> pth[100100];
int indeg[100100];
int loc[100100];
int ans[100100];

void merge(int a,int b) {
	if (cols[loc[a]].size()<cols[loc[b]].size()) swap(loc[a],loc[b]);
	for (auto &i:cols[loc[b]]) {
		cols[loc[a]].insert(i);	
	}	
}

void dfs(int idx) {
	for (auto i:pth[idx]) {
		dfs(i);
		merge(idx,i);
	}
	ans[idx]=cols[loc[idx]].size();
}

int main () {
	int n,m;
	scanf("%d%d",&n,&m);
	vector<int> cmp;
	for (int i=0;i<n;i++) {
		scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
		cmp.push_back(b[i]);
		cmp.push_back(d[i]);
	}
	for (int i=0;i<m;i++) {
		scanf("%d%d%d",&x[i],&y[i],&k[i]);
		cmp.push_back(y[i]);
	}
	sort(cmp.begin(),cmp.end());
	cmp.erase(unique(cmp.begin(),cmp.end()),cmp.end());
	for (int i=0;i<n;i++) {
		b[i]=lower_bound(cmp.begin(),cmp.end(),b[i])-cmp.begin();
		d[i]=lower_bound(cmp.begin(),cmp.end(),d[i])-cmp.begin();
	}
	for (int i=0;i<m;i++) {
		y[i]=lower_bound(cmp.begin(),cmp.end(),y[i])-cmp.begin();
	}

	vector<event> events;

	for (int i=0;i<n;i++) {
		events.push_back(event{a[i],i+1,b[i],d[i]});
		events.push_back(event{c[i]+1,-i-1,b[i],d[i]});
	}
	for (int i=0;i<m;i++) {
		events.push_back(event{x[i],100100,y[i],k[i]});
	}
	sort(events.begin(),events.end());
	
	int cnt=0;
	for (auto &e:events) {
		cnt++;
		//printf("-- %d %d %d %d\n",e.x,e.p,e.y1,e.y2);
		if (e.p==100100) {
			int idx = T.get(e.y1);
			//printf("---  %d\n",idx);
			if (idx!=-1) cols[idx].insert(e.y2);
		} else if (e.p>0) {
			int idx = T.get(e.y1);
			if (idx!=-1) {
				pth[idx].push_back(e.p);
				indeg[e.p]++;
			}
			T.add(1,0,size,e.y1,e.y2+1,node{cnt,e.p});
		} else {
			T.rem(1,0,size,e.y1,e.y2+1);
		}
	}

	for (int i=1;i<=n;i++) {
		loc[i]=i;
	}

	for (int i=1;i<=n;i++) {
		if (indeg[i]==0) dfs(i);
	}
	for (int i=1;i<=n;i++) {
		printf("%d\n",ans[i]);
	}
	return 0;
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:102:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
plahte.cpp:105:44: 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:110:36: 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.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 28260 KB Output is correct
2 Correct 132 ms 30628 KB Output is correct
3 Correct 17 ms 30628 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 34932 KB Output is correct
2 Correct 163 ms 35540 KB Output is correct
3 Correct 17 ms 35540 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 48020 KB Output is correct
2 Correct 268 ms 48020 KB Output is correct
3 Correct 17 ms 48020 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 67136 KB Output is correct
2 Correct 461 ms 67136 KB Output is correct
3 Correct 18 ms 67136 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 74448 KB Output is correct
2 Correct 406 ms 74448 KB Output is correct
3 Correct 18 ms 74448 KB Output is correct