oj.uz

Submission #412634

# Submission time Handle Problem Language Result Execution time Memory
412634 2021-05-27T08:51:07 Z pure_mem Plahte (COCI17_plahte) C++14
160 / 160
 502 ms 112732 KB 
#include <bits/stdc++.h>
 
#define ll long long
#define X first
#define Y second
#define MP make_pair
#define double long double
 
using namespace std;
 
const int N = 1e5 + 12, INF = 1e9;
            
struct node{
	vector< int > p;
	node* to[2] = {nullptr, nullptr};
	node* getp(int v){
		if(to[v] == nullptr) to[v] = new node();
		return to[v];
	}
	void upd(int tl, int tr, int l, int r, int val){
		if(tl > r || l > tr) return;
		if(tl >= l && tr <= r) return void(p.push_back(val));
		int tm = (tl + tr) / 2;
		getp(0)->upd(tl, tm, l, r, val);
		getp(1)->upd(tm + 1, tr, l, r, val);
	}
	void rem(int tl, int tr, int l, int r){
		if(tl > r || l > tr) return;
		if(tl >= l && tr <= r) return p.pop_back();
		int tm = (tl + tr) / 2;
		getp(0)->rem(tl, tm, l, r);
		getp(1)->rem(tm + 1, tr, l, r);
	}
	int get(int tl, int tr, int pos){
		if(tl == tr) return (p.empty() ? 0: p.back());
		int tm = (tl + tr) / 2;
		int val;
		if(pos <= tm) val = (to[0] ? to[0]->get(tl, tm, pos): 0);
		else val = (to[1] ? to[1]->get(tm + 1, tr, pos): 0);
		if(val == 0) val = (p.empty() ? 0: p.back());
		return val;
	}
}root;

int n, m, parent[N];
pair< pair<int, int>, pair<int, int> > p[N];
vector< pair< pair<int, int>, pair<int, int> > > g1;
vector< int > graph[N], clr[N];

int answer[N], was[N], last[N], T, res;

void add(int u){
	for(int v: clr[u]){
		if(last[v] != T) last[v] = T, res++;
	}
}
void rest(){
	T++, res = 0;
}

void inputs(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >> p[i].X.X >> p[i].X.Y >> p[i].Y.X >> p[i].Y.Y;
		g1.push_back(MP(MP(p[i].X.X, i), MP(p[i].X.Y, p[i].Y.Y)));
		g1.push_back(MP(MP(p[i].Y.X + 1, -i), MP(p[i].X.Y, p[i].Y.Y)));
	}
	unordered_map<int, int> mp;
	for(int i = 1, x, y, z;i <= m;i++){
		cin >> x >> y >> z; 
		if(!mp[z]) mp[z] = mp.size();
		z = mp[z];
		g1.push_back(MP(MP(x, N), MP(y, z)));	
	}
	sort(g1.begin(), g1.end());
	set< pair< pair<int, int>, int > > active, active2;
	for(auto tmp: g1){
		if(tmp.X.Y < 0){
			root.rem(1, INF, tmp.Y.X, tmp.Y.Y);		
		}	                           
		else if(tmp.X.Y != N){
		    int pr = root.get(1, INF, tmp.Y.X);
			if(pr) graph[pr].push_back(tmp.X.Y);
			root.upd(1, INF, tmp.Y.X, tmp.Y.Y, tmp.X.Y);		
		}
		else{
			int pr = root.get(1, INF, tmp.Y.X);
			if(pr) clr[pr].push_back(tmp.Y.Y);	
		}
	}
}

int sz[N], tin[N], tout[N], ord[N], timer;

void dfs1(int v){
	timer++;
	ord[timer] = v, tin[v] = timer;
	was[v] = 1, sz[v] = 1;
	for(int to: graph[v]){
		dfs1(to);
		sz[v] += sz[to];
	}
	tout[v] = timer;
}

void dfs2(int v, bool keep){
	int mx = 0;
	for(int to: graph[v]){
		if(sz[mx] < sz[to]) mx = to;
	}		
	for(int to: graph[v]){
		if(to != mx) dfs2(to, 0);
	}
	if(mx) dfs2(mx, 1);
	add(v);
	for(int to: graph[v]){
		if(to != mx){
			for(int i = tin[to];i <= tout[to];i++) add(ord[i]);	
		}
	}
	answer[v] = res;
	if(!keep) rest();
}

void prep(){
	rest();
	for(auto tmp: g1){
		int i = tmp.X.Y;
		if(i == N || i < 0 || was[i]) continue;
		dfs1(i); dfs2(i, 0);
	}
	for(int i = 1;i <= n;i++) cout << answer[i] << "\n";	
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 
	inputs();
	prep();
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 31800 KB Output is correct
2 Correct 126 ms 34048 KB Output is correct
3 Correct 4 ms 5028 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 45812 KB Output is correct
2 Correct 170 ms 46908 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 73924 KB Output is correct
2 Correct 295 ms 72400 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 112732 KB Output is correct
2 Correct 474 ms 97944 KB Output is correct
3 Correct 4 ms 5024 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 111060 KB Output is correct
2 Correct 502 ms 104388 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct