Submission #330745

#	Time	Username	Problem	Language	Result	Execution time	Memory
330745		htc001	Plahte (COCI17_plahte)	C++14	0 / 160	2101 ms	109704 KiB

plahte

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<pii,pii> p4i;
typedef pair<pll,pll> p4l;
const int N=150005;
int n,q,nx,ny;
p4l rec[N];
p4i mrec[N];
pll qr[N];
int tp[N];
pii mqr[N];
map<long long,int> mpx,mpy;
vector<int> ope[N*3][3];
int res[N],ans[N],p[N];
vector<int> nei[N];
set<int> ex[N],st[N];

const int maxn=N*6;
int m=1;
int lson[maxn],rson[maxn],val[maxn];

void build(int pos,int x,int y){
	val[pos]=-1;
	if(x==y) return;
	int mid=(x+y)>>1;
	build(lson[pos]=++m,x,mid);
	build(rson[pos]=++m,mid+1,y);
}

void pushdown(int pos){
	if(val[pos]!=-1){
		val[lson[pos]]=val[pos];
		val[rson[pos]]=val[pos];
		val[pos]=-1;
	}
}

void modify(int pos,int x,int y,int l,int r,int vl){
	if(x>=l&&y<=r){
		val[pos]=vl;
		return;
	}
	if(x>r||y<l) return;
	int mid=(x+y)>>1;
	pushdown(pos);
	modify(lson[pos],x,mid,l,r,vl);
	modify(rson[pos],mid+1,y,l,r,vl);
}

int query(int pos,int x,int y,int pl){
	if(x==y) return max(val[pos],0);
	int mid=(x+y)>>1;
	pushdown(pos);
	if(pl<=mid) return query(lson[pos],x,mid,pl);
	else return query(rson[pos],mid+1,y,pl);
}

void dfs(int x){
	res[x]=x;
	int hs=-1;
	for(int i=0;i<int(nei[x].size());i++){
		int to=nei[x][i];
		dfs(to);
		if(hs==-1||ans[hs]<ans[to]) hs=to;
	}
	if(hs!=-1) res[x]=res[hs];
	for(int i=0;i<int(nei[x].size());i++){
		int to=nei[x][i];
		if(to==hs) continue;
		for(set<int>::iterator it=st[res[hs]].begin();it!=st[res[hs]].end();it++) st[res[x]].insert(*it);
	}
	for(set<int>::iterator it=ex[x].begin();it!=ex[x].end();it++) st[res[x]].insert(*it);
	ans[x]=int(st[res[x]].size());
}

int main(){
//	freopen("b.in","r",stdin);
//	freopen("b.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		long long A,B,C,D;
		scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
		rec[i]=p4l(pll(A,B),pll(C,D));
		mpx[A];mpx[C];
		mpy[B];mpy[D];
	}
	for(int i=1;i<=q;i++){
		long long A,B;
		scanf("%lld%lld%d",&A,&B,tp+i);
		qr[i]=make_pair(A,B);
		mpx[A];mpy[B];
	}
	for(map<long long,int>::iterator it=mpx.begin();it!=mpx.end();it++) it->second=++nx;
	for(map<long long,int>::iterator it=mpy.begin();it!=mpy.end();it++) it->second=++ny;
	for(int i=1;i<=n;i++){
		mrec[i]=p4i(pii(mpx[rec[i].first.first],mpy[rec[i].first.second]),pii(mpx[rec[i].second.first],mpy[rec[i].second.second]));
		ope[mrec[i].first.first][0].push_back(i);
		ope[mrec[i].second.first][2].push_back(i);
	}
	for(int i=1;i<=q;i++){
		mqr[i]=pii(mpx[qr[i].first],mpy[qr[i].second]);
		ope[mqr[i].first][1].push_back(i);
	}
	build(1,1,ny);
	for(int i=1;i<=nx;i++){
		for(int j=0;j<int(ope[i][0].size());j++){
			int x=ope[i][0][j];
			p[x]=query(1,1,ny,mrec[x].first.second);
			nei[p[x]].push_back(x);
			modify(1,1,ny,mrec[x].first.second,mrec[x].second.second,x);
		}
		for(int j=0;j<int(ope[i][1].size());j++){
			int x=ope[i][1][j];
			ex[query(1,1,ny,mqr[x].second)].insert(tp[x]);
		}
		for(int j=0;j<int(ope[i][2].size());j++){
			int x=ope[i][2][j];
			modify(1,1,ny,mrec[x].first.second,mrec[x].second.second,p[x]);
		}
	}
	dfs(0);
	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}

/*
2 2
1 1 3 3
5 6 10 10
3 3 1
5 1 2

3 3
1 1 7 7
2 2 6 6
3 3 5 5
4 4 1
2 6 2
4 7 1

3 12
1 1 6 6
2 2 5 5
3 3 4 4
3 3 1
3 4 1
4 3 3
4 4 3
2 2 5
2 5 5
5 2 7
5 5 7
1 6 9
1 1 9
6 1 11
6 6 11
*/

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
plahte.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |   scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |   scanf("%lld%lld%d",&A,&B,tp+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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