Submission #1224716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224716		g4yuhg	Plahte (COCI17_plahte)	C++20	160 / 160	987 ms	42268 KiB

plahte

//Huyduocdithitp
#include <bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e9
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 21
//#define N 80004
#define N 100005
using namespace std;
bool ghuy4g;

struct Node {
	ll l, r, id, idx, dau, cuoi;
} p[N];
struct ban {
	ll fi, se, mau;
} a[N];
ll n, m, kq[N];

bool cmp2(ban A, ban B) {
	return A.fi > B.fi;
}

bool cmp(Node A, Node B) {
	if (A.dau == B.dau) {
		return A.r > B.r;
	}
	return A.dau > B.dau; // dau la dinh tren
}

map<ll, ll> bit;
ll mx = 1e9 + 5;

void update(ll u, ll v) {
	ll idx = u;
	if (idx <= 0) return;
	while (idx <= mx) {
		bit[idx] += v;
		idx += idx & (-idx);
	}
}

ll get(ll u) {
	ll idx = u, ans = 0;
	if (idx > mx) idx = mx;
	while (idx > 0) {
		if (bit.find(idx) != bit.end()) {
			ans += bit[idx];
		}
		idx -= idx & (-idx);
	}
	return ans;
}

void upd(ll l, ll r, ll v, ll o_v) {
	update(l, -o_v);
	update(r + 1, o_v);
	update(l, v);
	update(r + 1, -v);
}

struct CmpCuoiMin {
    bool operator()(const ll &i, const ll &j) const {
        return p[i].cuoi < p[j].cuoi;     // cuoi lớn -> ưu tiên thấp
    }
};

priority_queue<ll, vector<ll>, CmpCuoiMin> pq;

bool is[N]; // da co dinh nao vao no hay chua
vector<ll> vt, adj[N];
set<ll> s[N];

void combine(set<ll> &a, set<ll>& b) {
	if (a.size() >= b.size()) {
		for (auto it : b) {
			a.insert(it);
		}
	}
	else {
		for (auto it : a) {
			b.insert(it);
		}
		swap(a, b);
	}
}

void dfs1(ll u) {
	for (auto v : adj[u]) {
		dfs1(v);
		combine(s[u], s[v]);
		s[v].clear();
	}
	kq[u] = s[u].size();
}

bool klinh;

signed main(void) {
    faster;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
    	ll u, v, x, y;
    	cin >> u >> v >> x >> y;
    	p[i].r = x;
    	p[i].l = u;
    	p[i].dau = y;
    	p[i].cuoi = v;
    	vt.push_back(p[i].dau);
    	vt.push_back(p[i].cuoi);
    	p[i].id = i;
    }
    sort(p + 1, p + 1 + n, cmp);
    for (int i = 1; i <= n; i ++) {
    	//cout << p[i].cuoi << " " << p[i].dau << " " << p[i].l << " " << p[i].r << endl;
    }
    
    for (int i = 1; i <= m; i ++) {
    	cin >> a[i].fi >> a[i].se >> a[i].mau;
    	swap(a[i].fi, a[i].se);
    	vt.push_back(a[i].fi);
    }
    sort(a + 1, a + 1 + m, cmp2);
    sort(vt.begin(), vt.end(), greater<ll>());
    vt.resize(unique(vt.begin(), vt.end()) - vt.begin());
    
    ll cur_p = 1, cur_a = 1;
    
    for (auto it : vt) {
    	//cout << "su kien: " << it << endl;
    	while (p[cur_p].dau == it) {
    		ll x = get(p[cur_p].r);
    		if (1) {
    			if (x != 0) {
    				/*adj[p[cur_p].id].push_back(p[x].id); // chay xuong
    				//cout << p[cur_p].id << " " << p[x].id << endl;
    				if (is[p[x].id]) {
    					cout << "ngu";
    					exit(0);
    				}
    				is[p[x].id] = 1;*/
    				adj[p[x].id].push_back(p[cur_p].id);
    				if (is[p[cur_p].id]) {
    					cout << "ngu";
    					exit(0);
    				}
    				is[p[cur_p].id] = 1;
    			}
	    		p[cur_p].idx = x;
	    		upd(p[cur_p].l, p[cur_p].r, cur_p, x);
	    		pq.push(cur_p);
    		}
    		//cout << "add: " << p[cur_p].l << " " << p[cur_p].r << " " << p[cur_p].cuoi << endl;
    		cur_p ++ ;
    	}
    	while (a[cur_a].fi == it) {
    		ll x = get(a[cur_a].se);
    		if (x) {
	    		s[p[x].id].insert(a[cur_a].mau);
    		}
    		cur_a ++ ;
    	}
    	while (pq.size() && p[pq.top()].cuoi == it) {
    		ll j = pq.top();
    		pq.pop();
    		upd(p[j].l, p[j].r, p[j].idx, j);
    	}
    }
    
    for (int i = 1; i <= n; i ++) {
    	if (is[i]) continue;
    	dfs1(i);
    }
    
    for (int i = 1; i <= n; i ++) {
    	cout << kq[i] << endl;
    }
    
    
    cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
    return 0;
}

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