oj.uz

Submission #37460

# Submission time Handle Problem Language Result Execution time Memory
37460 2017-12-25T15:05:00 Z IvanC Plahte (COCI17_plahte) C++14
160 / 160
 519 ms 31404 KB 
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int> trinca;
typedef pair<int,int> ii;
typedef struct node* pnode;
const int MAXN = 1e5 + 10;
struct node{
	pnode l,r;
	int key,puro,junta,idx,prior;
	node(int _key,int _puro,int _idx) : l(NULL),r(NULL),key(_key),puro(_puro),junta(_puro),idx(_idx),prior( rand() ^ (rand() << 16) ) {}
};
inline int jnt(pnode t){return t ? t->junta : -0;}
inline void update(pnode t){if(t) t->junta = max(max(jnt(t->l),t->puro),jnt(t->r));}
void split(pnode t,int key,pnode &l,pnode &r){
	if(t == NULL){
		l = r = NULL;
	}
	else if(key < t->key){
		split(t->l,key,l,t->l);
		r = t;
	}
	else{
		split(t->r,key,t->r,r);
		l = t;
	}
	update(t);
}
void merge(pnode &t,pnode l,pnode r){
	if(l == NULL){
		t = r;
	}
	else if(r == NULL){
		t = l;
	}
	else if(l->prior > r->prior){
		merge(l->r,l->r,r);
		t = l;
	}
	else{
		merge(r->l,l,r->l);
		t = r;
	}
	update(t);
}
void insert(pnode &t,int key,int puro,int idx){
	pnode L,R;
	pnode aux = new node(key,puro,idx);
	split(t,key-1,L,R);
	merge(t,L,aux);
	merge(t,t,R);
}
void erase(pnode &t,int key){
	pnode L,mid,R;
	split(t,key-1,L,R);
	split(R,key,mid,R);
	merge(t,L,R);
}
int find(pnode t,int b){
	if(jnt(t->r) >= b) return find(t->r,b);
	if(t->puro >= b) return t->idx;
	return find(t->l,b);
}
int query(pnode &t,int a,int b){
	pnode L,R;
	split(t,a,L,R);
	int ret = -1;
	if(jnt(L) >= b) ret = find(L,b);
	merge(t,L,R);
	return ret;
}
int X1[MAXN],X2[MAXN],Y1[MAXN],Y2[MAXN],raiz[MAXN],resposta[MAXN],N;
int XC[MAXN],YC[MAXN],COR[MAXN],M;
vector<int> grafo[MAXN],armazenado[MAXN];
set<int> *conjunto[MAXN];
vector<trinca> sweep;
pnode Treap;
void dfs(int v){
	int mx = -1, big = -1;
	for(int u : grafo[v]){
		dfs(u);
		int szu = conjunto[u]->size();
		if(szu > mx){
			mx = szu;
			big = u;
		}
	}
	if(big == -1){
		conjunto[v] = new set<int>();
		for(int i : armazenado[v]) conjunto[v]->insert(i);
	}
	else{
		conjunto[v] = conjunto[big];
		for(int i : armazenado[v]) conjunto[v]->insert(i);
	}
	for(int u : grafo[v]){
		if(u == big) continue;
		for(set<int>::iterator it = conjunto[u]->begin();it != conjunto[u]->end();it++){
			conjunto[v]->insert(*it);
		}
	}
	resposta[v] = conjunto[v]->size();
}
int main(){
	Treap = NULL;
	scanf("%d %d",&N,&M);
	for(int i = 1;i<=N;i++){
		scanf("%d %d %d %d",&X1[i],&Y1[i],&X2[i],&Y2[i]);
		raiz[i] = 1;
		sweep.push_back(make_tuple(X1[i],0,i));
		sweep.push_back(make_tuple(X2[i],2,i));
	}
	for(int i = 1;i<=M;i++){
		scanf("%d %d %d",&XC[i],&YC[i],&COR[i]);
		sweep.push_back(make_tuple(XC[i],1,i));
	}
	sort(sweep.begin(),sweep.end());
	for(int evento = 0;evento<sweep.size();evento++){
		int op = get<1>(sweep[evento]), idx = get<2>(sweep[evento]);
		if(op == 0){
			int last = query(Treap,Y1[idx],Y2[idx]);
			if(last != -1){
				raiz[idx] = 0;
				grafo[last].push_back(idx);
			}
			insert(Treap,Y1[idx],Y2[idx],idx);
		}
		else if(op == 1){
			int last = query(Treap,YC[idx],YC[idx]);
			if(last != -1){
				armazenado[last].push_back(COR[idx]);
			}
		}
		else{
			erase(Treap,Y1[idx]);
		}
	}
	for(int i = 1;i<=N;i++){
		if(raiz[i]) dfs(i);
	}
	for(int i = 1;i<=N;i++){
		printf("%d\n",resposta[i]);
	}
	return 0;
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:117:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int evento = 0;evento<sweep.size();evento++){
                           ^
plahte.cpp:105:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
plahte.cpp:107:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&X1[i],&Y1[i],&X2[i],&Y2[i]);
                                                   ^
plahte.cpp:113:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&XC[i],&YC[i],&COR[i]);
                                          ^

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 17116 KB Output is correct
2 Correct 106 ms 18172 KB Output is correct
3 Correct 3 ms 11012 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 18472 KB Output is correct
2 Correct 169 ms 18516 KB Output is correct
3 Correct 0 ms 11012 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 24904 KB Output is correct
2 Correct 229 ms 23888 KB Output is correct
3 Correct 0 ms 11012 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 31404 KB Output is correct
2 Correct 406 ms 28820 KB Output is correct
3 Correct 0 ms 11012 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 30260 KB Output is correct
2 Correct 459 ms 30256 KB Output is correct
3 Correct 0 ms 11012 KB Output is correct