Submission #1224404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224404		g4yuhg	Plahte (COCI17_plahte)	C++20	0 / 160	120 ms	21364 KiB

plahte

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long 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 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], b[N];
ll cnt[N], in[N], out[N], st[6 * N], f[6 * N], timeDfs;

void lazy(ll id, ll l, ll r) {
	if (f[id] == 0) return;
	f[id * 2] += f[id];
	f[id * 2 + 1] += f[id];
	st[id] += f[id] * (r - l + 1);
	f[id] = 0;
}
void update(ll id, ll l, ll r, ll L, ll R, ll v) {
	lazy(id, l, r);
	if (l > R || r < L) return;
	if (L <= l && r <= R) {
		f[id] += v;
		lazy(id, l, r);
		return;
	}
	ll mid = (l + r) / 2;
	update(id * 2, l, mid, L, R, v);
	update(id * 2 + 1, mid + 1, r, L, R, v);
	st[id] = st[id * 2] + st[id * 2 + 1];
}
ll get(ll id, ll l, ll r, ll i) {
	lazy(id, l, r);
	if (i > r || i < l) return 0;
	if (l == r) {
		return st[id];
	}
	ll mid = (l + r) / 2;
	return get(id * 2, l, mid, i) + get(id * 2 + 1, mid + 1, r, i);
}

void dfs(ll u) {
	in[u] = ++ timeDfs;
	for (auto v : adj[u]) {
		dfs(v);
	}
	out[u] = timeDfs;
}

void dfs1(ll u) {
	for (auto it : b[u]) {
		cnt[it] ++ ;
		if (cnt[it] == 1) {
			update(1, 1, n, in[u], out[u], 1);
		}
	}
	for (auto v : adj[u]) {
		dfs1(v);
	}
	for (auto it : b[u]) {
		cnt[it] -- ;
	}
}

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 (p[x].id < p[cur_p].id) {
    			if (x != 0) {
    				adj[p[cur_p].id].push_back(p[x].id); // chay xuong
    				//cout << p[cur_p].id << " " << p[x].id << endl;
    				is[p[x].id] = 1;
    			}
	    		p[cur_p].idx = x;
	    		upd(p[cur_p].l, p[cur_p].r, cur_p, x);
	    		pq.push(cur_p);
    		}
    		else { // tuc la co tam phu, nhung tam phu xuat hien sau
    			adj[p[x].id].push_back(p[cur_p].id);
    			is[p[cur_p].id] = 1;
    			//cout << p[x].id << " " << p[cur_p].id << endl;
    		}
    		//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);
    		kq[p[x].id] = a[cur_a].mau;
    		b[p[x].id].push_back(a[cur_a].mau);
    		//cout << "to: " << a[cur_a].se << " " << a[cur_a].mau << endl;
    		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;
    	dfs(i);
    }
    
    for (int i = 1; i <= n; i ++) {
    	if (is[i]) continue;
    	dfs1(i);
    }
    
    for (int i = 1; i <= n; i ++) {
    	cout << get(1, 1, n, in[i]) << endl;
    }
    
    
    cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
    return 0;
}

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