oj.uz

Submission #165608

# Submission time Handle Problem Language Result Execution time Memory
165608 2019-11-27T16:58:52 Z manh9203 Plahte (COCI17_plahte) C++17
160 / 160
 1562 ms 96272 KB 
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 3e5 + 5;
struct reg{
	int lx, ly, rx, ry;
} reg[N];
struct point{
	int x, y, color;
} p[N];
int n,m,st[4*N],lazy[4*N],par[N],ans[N];
vector<int> dmx,dmy,add[N],sub[N],pnt[N],adj[N];
map<int,int> idx,idy;
set<int> s[N];
//IT seg
void push_down(int id,int l,int r){
	if(lazy[id] != -1){
		st[id] = lazy[id];
		if(l < r){
			lazy[id<<1] = lazy[id];
			lazy[id<<1|1] = lazy[id];
		}
		lazy[id] = -1;
	}
}
void update(int id,int l,int r,int i,int j,int val){
	push_down(id, l, r);
	if(l>j || r<i || i>j){
		return;
	}
	if(l>=i && r<=j){
		st[id] = val;
		if(l < r){
			lazy[id<<1] = val;
			lazy[id<<1|1] = val;
		}
		return;
	}
	int mid = (l + r) >> 1;
	update(id<<1, l, mid, i, j, val);
	update(id<<1|1, mid+1, r, i, j, val);
	st[id] = max(st[id<<1], st[id<<1|1]);
}
int get(int id,int l,int r,int i,int j){
	push_down(id, l, r);
	if(l>j || r<i || i>j){
		return -1e9;
	}
	if(l>=i && r<=j){
		return st[id];
	}
	int mid = (l + r) >> 1;
	return max(get(id<<1, l, mid, i, j), get(id<<1|1, mid+1, r, i, j));
}
//gop set
void dfs(int u){
	for(int v: adj[u]){
		dfs(v);
	}
	for(int v: adj[u]){
		if(s[u].size() < s[v].size()){
			swap(s[u], s[v]);
		}
	}
	for(int v: adj[u]){
		for(int w: s[v]){
			s[u].insert(w);
		}
	}
	ans[u] = s[u].size();
}
//main
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> reg[i].lx >> reg[i].ly >> reg[i].rx >> reg[i].ry;
		if(idx[reg[i].lx] == 0){
			dmx.push_back(reg[i].lx);
			idx[reg[i].lx] = 1;
		}
		if(idy[reg[i].ly] == 0){
			dmy.push_back(reg[i].ly);
			idy[reg[i].ly] = 1;
		}
		if(idx[reg[i].rx] == 0){
			dmx.push_back(reg[i].rx);
			idx[reg[i].rx] = 1;
		}
		if(idy[reg[i].ry] == 0){
			dmy.push_back(reg[i].ry);
			idy[reg[i].ry] = 1;
		}
	}
	int dem = 0;
	for(int i=1;i<=m;i++){
		cin >> p[i].x >> p[i].y >> p[i].color;
		if(idx[p[i].x] == 0){
			dmx.push_back(p[i].x);
			idx[p[i].x] = 1;
		}
		if(idy[p[i].y] == 0){
			dmy.push_back(p[i].y);
			idy[p[i].y] = 1;
		}
	}
	sort(dmx.begin(), dmx.end());
	sort(dmy.begin(), dmy.end());
	for(int i=0;i<dmx.size();i++){
		idx[dmx[i]] = i + 1;
	}
	for(int i=0;i<dmy.size();i++){
		idy[dmy[i]] = i + 1;
	}
	for(int i=1;i<=n;i++){
		reg[i].lx = idx[reg[i].lx]; reg[i].rx = idx[reg[i].rx];
		reg[i].ly = idy[reg[i].ly]; reg[i].ry = idy[reg[i].ry];
		add[reg[i].lx].push_back(i);
		sub[reg[i].rx].push_back(i);
	}
	for(int i=1;i<=m;i++){
		p[i].x = idx[p[i].x];
		p[i].y = idy[p[i].y];
		pnt[p[i].x].push_back(i);
	}
	int h = dmy.size(), len = dmx.size();
	for(int i=1;i<=len;i++){
		for(int j: add[i]){
			int pre = get(1, 1, h, reg[j].ly, reg[j].ry);
			adj[pre].push_back(j);
			par[j] = pre;
			update(1, 1, h, reg[j].ly, reg[j].ry, j);
		}
		for(int j: pnt[i]){
			int now = get(1, 1, h, p[j].y, p[j].y);
			s[now].insert(p[j].color);
		}
		for(int j: sub[i]){
			update(1, 1, h, reg[j].ly, reg[j].ry, par[j]);
		}
	}
	for(int i=1;i<=n;i++){
		if(par[i] == 0){
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++){
		cout << ans[i] << "\n";
	}
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:110:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<dmx.size();i++){
              ~^~~~~~~~~~~
plahte.cpp:113:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<dmy.size();i++){
              ~^~~~~~~~~~~
plahte.cpp:96:6: warning: unused variable 'dem' [-Wunused-variable]
  int dem = 0;
      ^~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 59396 KB Output is correct
2 Correct 362 ms 59492 KB Output is correct
3 Correct 41 ms 42616 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 62360 KB Output is correct
2 Correct 429 ms 61820 KB Output is correct
3 Correct 41 ms 42616 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 78284 KB Output is correct
2 Correct 815 ms 70504 KB Output is correct
3 Correct 43 ms 42616 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1540 ms 96272 KB Output is correct
2 Correct 1562 ms 91900 KB Output is correct
3 Correct 40 ms 42744 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1400 ms 95284 KB Output is correct
2 Correct 1270 ms 87232 KB Output is correct
3 Correct 41 ms 42616 KB Output is correct