제출 #1137000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137000		vako_p	Plahte (COCI17_plahte)	C++20	160 / 160	302 ms	131528 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e6 + 5;
ll n,m,a[mxN],b[mxN],c[mxN],d[mxN],p[mxN][25],ans[mxN];
map<ll,vector<pair<ll,pair<ll,ll>>>> mp;
set<pair<ll,ll>> s;
pair<ll,pair<ll,ll>> q[mxN];
vector<ll> v[mxN];
set<ll> ss[mxN];

void dfs(ll at){
	for(auto it : v[at]){
		dfs(it);
		if(ss[at].size() < ss[it].size()) swap(ss[at], ss[it]);
		for(auto k : ss[it]) ss[at].insert(k);
		ss[it].clear();
	}
	ans[at] = ss[at].size();
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		mp[a[i]].pb({b[i], {i, 0}});
	}
	for(int i = 0; i < m; i++){
		cin >> q[i].first >> q[i].second.first >> q[i].second.second;
		mp[q[i].first].pb({q[i].second.first, {q[i].second.second, 2}});
	}
	for(auto it : mp) sort(it.second.begin(), it.second.end());
	for(int i = 1; i <= n; i++) mp[c[i]].pb({b[i], {i, 1}});
	c[0] = d[0] = 2e9;
	s.insert({0, 0});
	for(auto itt : mp){
		for(auto num : itt.second){
			if(num.second.second == 1){
				s.erase({num.first, num.second.first});
				continue;
			}
			pair<ll,ll> it = {num.first, num.second.first};
			auto it1 = s.upper_bound({it.first, 2e9}); --it1;
			ll x = (*it1).second;
			if(d[x] >= it.first){
				if(num.second.second == 2){
					ss[x].insert(it.second);
					continue;
				}
				p[it.second][0] = x;
				v[x].pb(it.second);
			}
			else{
				for(int i = 19; i >= 0; i--){
					if(d[p[x][i]] < it.first) x = p[x][i];
				}
				if(num.second.second == 2){
					ss[p[x][0]].insert(it.second);
					continue;
				}
				p[it.second][0] = p[x][0];
				v[p[x][0]].pb(it.second);
			}
			for(int i = 1; i < 20; i++) p[it.second][i] = p[p[it.second][i - 1]][i - 1];
			s.insert(it);
		}
	}
	dfs(0);
	for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
} 

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