#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define a2 array<int,2>
#define a3 array<int,3>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 200100;
const int PW = 20;
const int oo = 2e9;
unordered_map<int, vector<int> > ver;
vector<int> vf, cols[N], g[N];
int a[N], b[N], c[N], d[N], n, m, nm[N], id, pre[N], tin[N], tout[N], tt = 0, up[N][PW];
int ans[N], ad[N], del[N];
bool cmp(int _x, int _y){
return a[_x] < a[_y];
}
bool cmp1(int _x, int _y){
return tin[_x] < tin[_y];
}
struct seg_tree{
vector<int> elements;
vector<a2> mn;
seg_tree(): elements(0), mn(0) {}
void real_build(){
sort(all(elements));
elements.resize(unique(all(elements)) - elements.begin());
mn.resize(sz(elements) * 4 + 10);
for (int it = 1; it < sz(mn); it++)
mn[it] = {-oo, oo};
}
void real_search(int v, int l, int r, int vlt){
if (l == r){
id = mn[v][1];
return;
}
int md = (l + r) >> 1;
if (mn[v + v + 1][0] >= vlt)
real_search(v + v + 1, md + 1, r, vlt);
else real_search(v + v, l, md, vlt);
}
void search(int v, int l, int r, int vls, int vlt){
if (elements[l] > vls || id >= 0) return;
if (elements[r] <= vls){
if (mn[v][0] >= vlt)
real_search(v, l, r, vlt);
return;
}
int md = (l + r) >> 1;
search(v + v + 1, md + 1, r, vls, vlt);
search(v + v, l, md, vls, vlt);
}
void update(int v, int l, int r, int vls, int vlt){
if (l == r){
mn[v] = {vlt, id};
return;
}
int md = (l + r) >> 1;
if (elements[md] >= vls)
update(v + v, l, md, vls, vlt);
else update(v + v + 1, md + 1, r, vls, vlt);
mn[v] = max(mn[v + v], mn[v + v + 1]);
}
};
seg_tree st[4 * N];
void build(int v, int l, int r, int vlf, int vls){
st[v].elements.PB(vls);
if (l == r) return;
int md = (l + r) >> 1;
if (vlf <= vf[md])
build(v + v, l, md, vlf, vls);
else build(v + v + 1, md + 1, r, vlf, vls);
}
void real_build(int v, int l, int r){
st[v].real_build();
if (l == r) return;
int md = (l + r) >> 1;
real_build(v + v, l, md);
real_build(v + v + 1, md + 1, r);
}
void search(int v, int l, int r, int vlf, int vls, int vlt){
if (vlf > vf[r] || id >= 0) return;
if (vlf <= vf[l]){
st[v].search(1, 0, sz(st[v].elements) - 1, vls, vlt);
return;
}
int md = (l + r) >> 1;
search(v + v, l, md, vlf, vls, vlt);
search(v + v + 1, md + 1, r, vlf, vls, vlt);
}
void update(int v, int l, int r, int vlf, int vls, int vlt){
st[v].update(1, 0, sz(st[v].elements) - 1, vls, vlt);
if (l == r) return;
int md = (l + r) >> 1;
if (vf[md] >= vlf)
update(v + v, l, md, vlf, vls, vlt);
else update(v + v + 1, md + 1, r, vlf, vls, vlt);
}
void dfs(int v){
tin[v] = ++tt;
if (v != 0) {
for (int po = 1; po < PW; po++)
up[v][po] = up[up[v][po - 1]][po - 1];
}
for (int u : g[v])
dfs(u);
tout[v] = ++tt;
}
bool upper(int a, int b){
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int a, int b){
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int po = PW - 1; po >= 0; po--)
if (!upper(up[a][po], b))
a = up[a][po];
return up[a][0];
}
void last_dfs(int v){
ans[v] = ad[v];
if (v > 0)
ans[up[v][0]] -= del[v];
for (int u : g[v]){
last_dfs(u);
ans[v] += ans[u];
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
vf.PB(c[i]);
nm[i] = i;
}
for (int i = n; i < n + m; i++){
cin >> a[i] >> b[i] >> c[i];
vf.PB(a[i]);
nm[i] = i;
}
sort(all(vf));
vf.resize(unique(all(vf)) - vf.begin());
sort(nm, nm + n + m, cmp);
for (int it = 0; it < n + m; it++) {
int i = nm[it];
if (i < n)
build(1, 0, sz(vf) - 1, c[i], b[i]);
else build(1, 0, sz(vf) - 1, a[i], b[i]);
}
real_build(1, 0, sz(vf) - 1);
for (int it = 0; it < n + m; it++){
int i = nm[it];
if (i < n){
id = -1;
search(1, 0, sz(vf) - 1, c[i], b[i], d[i]);
pre[i] = id;
id = i;
update(1, 0, sz(vf) - 1, c[i], b[i], d[i]);
} else {
id = -1;
search(1, 0, sz(vf) - 1, a[i], b[i], b[i]);
if (id >= 0)
cols[id].PB(c[i]);
}
}
for (int i = 0; i < n; i++){
g[pre[i] + 1].PB(i + 1);
up[i + 1][0] = pre[i] + 1;
if (sz(cols[i]) == 0) continue;
for (int cl : cols[i])
if (sz(ver[cl]) == 0 || ver[cl].back() != i + 1)
ver[cl].PB(i + 1);
}
dfs(0);
for (int i = 1; i <= n; i++)
cerr << i << " " << up[i][0] << '\n';
for (auto EL : ver){
vector<int> &vc = EL.second;
sort(all(vc), cmp1);
int glc = vc[0];
ad[vc[0]]++;
del[vc[0]]++;
for (int it = 1; it < sz(vc); it++){
int v = vc[it];
int pr = vc[it - 1];
int lc = lca(v, pr);
if (!upper(glc, lc)){
ad[up[glc][0]]++;
del[lc]++;
}
ad[lc]--;
ad[v]++;
}
ad[up[glc][0]]++;
del[0]++;
}
last_dfs(0);
for (int i = 1; i <= n; i++)
cout << ans[i] << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
441 ms |
97860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
527 ms |
104368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
929 ms |
146296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1509 ms |
209752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1506 ms |
209396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
