oj.uz

답안 #53003

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53003 2018-06-27T14:11:45 Z hamzqq9 Plahte (COCI17_plahte) C++14
160 / 160
 387 ms 35044 KB 
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1050000001
#define N 80005
#define LOG 19
#define magic 100
#define KOK 350
#define EPS 0.000000000001
#define pw(x) 1ll*((1ll)<<(x))
#define PI 3.1415926535
using namespace std;

struct rect {
	
	int a,b,c,d;

	vector<int> ch;

	set<int> colors;

} R[N];

struct point {

	int x,y,c;

} P[N];

int n,m,cnt;
int lazy[N*4],S[N*4],ans[N],vis[N],ata[N];
vector<int> Compressed;
vector<ii> eventP;
vector<iii> eventR;

void push(int node,int bas,int son) {

	if(~lazy[node]) {

		S[node*2]=S[node*2+1]=lazy[node*2]=lazy[node*2+1]=lazy[node];

		lazy[node]=-1;

	}

}

void up(int node,int bas,int son,int x,int y,int val) {

	if(x>y) return ;

	if(bas>y || son<x) return ;

	if(bas>=x && son<=y) {

		lazy[node]=S[node]=val;

		return ;

	}

	push(node,bas,son);

	up(node*2,bas,orta,x,y,val);
	up(node*2+1,orta+1,son,x,y,val);

}

int get(int node,int bas,int son,int x) {

	if(x<1 || x>cnt) return 0;

	if(bas==x && son==x) return S[node];
	
	push(node,bas,son);

	if(x<=orta) return get(node*2,bas,orta,x);

	return get(node*2+1,orta+1,son,x);

}

void merge(set<int> &to,set<int> &from) {

	for(auto x:from) {

		if(to.find(x)==to.end()) to.insert(x);

	}

	from.clear();

}

void dfs(int node) {

	//assert(!vis[node]);

	vis[node]=1;

	for(int go:R[node].ch) {

		dfs(go);

		if(sz(R[go].colors)>sz(R[node].colors)) swap(R[go].colors,R[node].colors);

		merge(R[node].colors,R[go].colors);

	}

	ans[node]=sz(R[node].colors);

}

int main() {

	#if 0
	freopen("input.txt","r",stdin);
 	#endif

 	fill(lazy,lazy+N*4,-1);

	scanf("%d %d",&n,&m);

	for(int i=1;i<=n;i++) {

		scanf("%d %d %d %d",&R[i].a,&R[i].b,&R[i].c,&R[i].d);

		eventR.pb({{R[i].b,i},0});

		eventR.pb({{R[i].d+1,i},-1});

	} 

	for(int i=1;i<=m;i++) {

		scanf("%d %d %d",&P[i].x,&P[i].y,&P[i].c);

	}

	sort(P+1,P+1+m,[](point x,point y) {

		return x.x<y.x;

	});

	for(int i=1;i<=m;i++) {

		eventP.pb({P[i].y,i});

	}

	for(int i=1;i<=m;i++) {

		++cnt;

		while(i+1<=m && P[i].x==P[i+1].x) P[i].x=cnt,i++;

		Compressed.pb(P[i].x);

		P[i].x=cnt;

	}

	for(int i=1;i<=n;i++) {

		int x1=lower_bound(all(Compressed),R[i].a)-Compressed.begin()+1;

		int x2=upper_bound(all(Compressed),R[i].c)-Compressed.begin();

		R[i].a=x1;

		R[i].c=x2;

	}

	sort(all(eventR),[](iii x,iii y) {

		if(x.st.st<y.st.st) return true;

		if(x.st.st>y.st.st) return false;

		if(x.nd<y.nd) return true;

		return false;

	});

	sort(all(eventP));

	int last=-1;

	for(int i=0;i<sz(eventR);i++) {

		int id=eventR[i].st.nd;
		int x1=R[id].a;
		int x2=R[id].c;

		while(last+1<sz(eventP) && eventR[i].st.st>eventP[last+1].st) {

			last++;

		//	dbg(eventP[last].st);
		//	dbg(eventR[i].st.st);

			int curR=get(1,1,cnt,P[eventP[last].nd].x);

			R[curR].colors.insert(P[eventP[last].nd].c);

		}

		//dbg(last);
		
		if(eventR[i].nd==0) {

			int cur=get(1,1,cnt,x1);

			R[cur].ch.pb(id);

			ata[id]=cur;

			up(1,1,cnt,x1,x2,id);

		}
		else {

			up(1,1,cnt,x1,x2,ata[id]);

		}

	}

	for(int i=1;i<=n;i++) {

		if(!ata[i]) {

			dfs(i);

		}

	}

	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);

}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:150: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:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&R[i].a,&R[i].b,&R[i].c,&R[i].d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&P[i].x,&P[i].y,&P[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 12268 KB Output is correct
2 Correct 122 ms 13856 KB Output is correct
3 Correct 10 ms 13856 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 15204 KB Output is correct
2 Correct 139 ms 16216 KB Output is correct
3 Correct 9 ms 16216 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 21588 KB Output is correct
2 Correct 212 ms 21588 KB Output is correct
3 Correct 9 ms 21588 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 385 ms 30680 KB Output is correct
2 Correct 359 ms 30680 KB Output is correct
3 Correct 10 ms 30680 KB Output is correct

Subtask #5
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 346 ms 33948 KB Output is correct
2 Correct 387 ms 35044 KB Output is correct
3 Correct 11 ms 35044 KB Output is correct