oj.uz

Submission #332298

# Submission time Handle Problem Language Result Execution time Memory
332298 2020-12-02T01:44:57 Z htc001 Plahte (COCI17_plahte) C++14
160 / 160
 549 ms 87524 KB 
#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];
long long mpx[N*3],mpy[N*3];
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[to]].begin();it!=st[res[to]].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(){
	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[++nx]=A;mpx[++nx]=C;
		mpy[++ny]=B;mpy[++ny]=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[++nx]=A;mpy[++ny]=B;
	}
	sort(mpx+1,mpx+1+nx);
	sort(mpy+1,mpy+1+ny);
	nx=unique(mpx+1,mpx+1+nx)-mpx;
	ny=unique(mpy+1,mpy+1+ny)-mpy;
	for(int i=1;i<=n;i++){
		mrec[i]=p4i(pii(lower_bound(mpx+1,mpx+1+nx,rec[i].first.first)-mpx,lower_bound(mpy+1,mpy+1+ny,rec[i].first.second)-mpy)
				   ,pii(lower_bound(mpx+1,mpx+1+nx,rec[i].second.first)-mpx,lower_bound(mpy+1,mpy+1+ny,rec[i].second.second)-mpy));
		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(lower_bound(mpx+1,mpx+1+nx,qr[i].first)-mpx,lower_bound(mpy+1,mpy+1+ny,qr[i].second)-mpy);
		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;
}

Compilation message

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

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 60780 KB Output is correct
2 Correct 175 ms 61036 KB Output is correct
3 Correct 33 ms 49772 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 63360 KB Output is correct
2 Correct 190 ms 62316 KB Output is correct
3 Correct 33 ms 49772 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 73520 KB Output is correct
2 Correct 314 ms 69356 KB Output is correct
3 Correct 33 ms 49772 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 87524 KB Output is correct
2 Correct 546 ms 82924 KB Output is correct
3 Correct 33 ms 49900 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 85720 KB Output is correct
2 Correct 505 ms 80492 KB Output is correct
3 Correct 34 ms 49920 KB Output is correct