Submission #37460

#TimeUsernameProblemLanguageResultExecution timeMemory
37460IvanCPlahte (COCI17_plahte)C++14
160 / 160
519 ms31404 KiB
#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 (stderr)

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]);
                                          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...