Submission #745667

#	Time	Username	Problem	Language	Result	Execution time	Memory
745667		esomer	Plahte (COCI17_plahte)	C++17	160 / 160	1558 ms	79060 KiB

plahte

#include<bits/stdc++.h>
 
using namespace std;
 
//~ #define endl "\n"

typedef long long ll;
typedef long double ld;

const int MOD = 1e9 + 7;

struct segTree{
	vector<pair<int, int>> v;
	vector<set<pair<int, int>>> all;
	int size;
	void init(int n){
		size = 1;
		while(size < n) size *= 2;
		v.assign(2 * size, {1e9, 1e9});
		all.resize(2 * size);
	}
	
	void sett(int i, pair<int, int> p, int x, int lx, int rx){
		if(rx - lx == 1){
			all[x].insert(p);
			v[x] = *all[x].begin();
			return;
		}
		int m = (lx + rx) / 2;
		if(i < m) sett(i, p, 2 * x + 1, lx, m);
		else sett(i, p, 2 * x + 2, m, rx);
		v[x] = min(v[2 * x + 1], v[2 * x + 2]);
	}
	
	void sett(int i, pair<int, int> p){
		sett(i, p, 0, 0, size);
	}
	
	void eras(int i, pair<int, int> p, int x, int lx, int rx){
		if(rx - lx == 1){
			all[x].erase(p);
			if((int)all[x].size() > 0) v[x] = *all[x].begin();
			else v[x] = {1e9, 1e9};
			return;
		}
		int m = (lx + rx) / 2;
		if(i < m) eras(i, p, 2 * x + 1, lx, m);
		else eras(i, p, 2 * x + 2, m, rx);
		v[x] = min(v[2 * x + 1], v[2 * x + 2]);
	}
	
	void eras(int i, pair<int, int> p){
		eras(i, p, 0, 0, size);
	}
	
	pair<int, int> calc(int l, int r, int x, int lx, int rx){
		if(lx >= l && rx <= r) return v[x];
		else if(lx >= r || rx <= l) return {1e9, 1e9};
		int m = (lx + rx) / 2;
		pair<int, int> p1 = calc(l, r, 2 * x + 1, lx, m);
		pair<int, int> p2 = calc(l, r, 2 * x + 2, m, rx);
		return min(p1, p2);
	}
	
	pair<int, int> calc(int l, int r){
		return calc(l, r, 0, 0, size);
	}
};

void DFS(int x, vector<vector<int>>& adj, vector<bool>& vis, vector<set<int>>& colors, vector<int>& ans){
	//~ cout << "X " << x << endl;
	//~ cout << "Colors: " << endl;
	//~ for(int y : colors[x]) cout << y << " "; cout << endl;
	vis[x] = 1;
	for(int node : adj[x]){
		//~ cout << "X " << x << " node " << node << endl;
		if(!vis[node]){
			DFS(node, adj, vis, colors, ans);
			if((int)colors[node].size() > (int)colors[x].size()) swap(colors[x], colors[node]);
			for(int y : colors[node]){
				colors[x].insert(y);
			}
			//~ cout <<"X " << x << " node " << node << " colors " << endl;
			//~ for(int y: colors[x]) cout << y << " "; cout << endl;
		}
	}
	ans[x] = (int)colors[x].size();
}

void solve(){
	int n, m; cin >> n >> m;
	vector<tuple<int, int, int, int, int>> v(n + m);
	vector<int> heights;
	for(int i = 0; i < n; i++){
		int a, b, c, d; cin >> a >> b >> c >> d;
		v[i] = {a, d, c, b, i};
		heights.push_back(b); heights.push_back(d);
	}
	vector<vector<int>> adj(n+m);
	vector<set<int>> colors(n + m);
	vector<int> deg(n+m, 0);
	for(int i = 0; i < m; i++){
		int a, b, c; cin >> a >> b >> c;
		heights.push_back(b);
		colors[n + i].insert(c);
		v[n+i] = {a, 1e9, b, -1, n+i};
	}
	sort(v.begin(), v.end());
	int mx_height = 0;
	int lst = -1;
	map<int, int> ind;
	sort(heights.begin(), heights.end());
	for(int i = 0; i < (int)heights.size(); i++){
		if(heights[i] != lst){
			ind[heights[i]] = mx_height;
			//~ cout << "heights[i] " << heights[i] << " ind " << ind[heights[i]] << endl;
			mx_height++;
		}
		lst = heights[i];
	}
	segTree st; st.init(mx_height);
	priority_queue<tuple<int, int, int, int>> q;
	int curr = 0;
	for(int i = 0; i < n + m; i++){
		//~ cout << "I " << i << endl;
		while(q.empty() == false && -get<0>(q.top()) < get<0>(v[i])){
			int up = ind[get<1>(q.top())];
			int down = ind[get<2>(q.top())];
			int id = get<3>(q.top());
			//~ cout << "Removing " << get<1>(q.top()) << " " << get<2>(q.top()) << " " << get<3>(q.top()) << endl;
			st.eras(up, {down, id});
			q.pop();
		}
		int height = get<1>(v[i]);
		if(get<3>(v[i]) == -1) height = get<2>(v[i]);
		int lo = ind[height];
		int hi = mx_height - 1;
		int bst = -1;
		while(lo <= hi){
			int mid = (lo + hi) / 2;
			pair<int, int> p = st.calc(ind[height], mid + 1); 
			int low = get<3>(v[i]);
			if(get<3>(v[i]) == -1) low = get<2>(v[i]);
			if(p.first <= ind[low]){
				bst = p.second;
				hi = mid - 1;
			}else lo = mid + 1;
		}
		//~ cout << "I " << i << " ind " << get<4>(v[i]) << " bst " << bst << endl;
		if(bst != -1) {adj[bst].push_back(get<4>(v[i])); deg[get<4>(v[i])]++;}
		if(get<3>(v[i]) != -1){
			//Add it into the segment tree.
			//~ cout << "Inserting at height " << get<1>(v[i]) << " " << get<3>(v[i]) << " " << get<4>(v[i]) << endl;
			q.push({-get<2>(v[i]), get<1>(v[i]), get<3>(v[i]), get<4>(v[i])});
			//~ cout << "Here" << endl;
			st.sett(ind[get<1>(v[i])], {ind[get<3>(v[i])], get<4>(v[i])});
			//~ cout << "Here2" << endl;
		}
	}
	//~ cout << "OUT" << endl;
	vector<bool> vis(n+m, 0);
	vector<int> ans(n+m);
	for(int i = 0; i < n; i++){
		if(!deg[i]){
			DFS(i, adj, vis, colors, ans);
		}
	}
	for(int i = 0; i < n; i++) cout << ans[i] << endl;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    //~ int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        solve();
    }
}

Compilation message (stderr)

plahte.cpp: In function 'void solve()':
plahte.cpp:123:6: warning: unused variable 'curr' [-Wunused-variable]
  123 |  int curr = 0;
      |      ^~~~

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32