//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 80004
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |