This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
const int N = 160010;
namespace BIT2D {
vector<int> val[N];
vector<int> bit[N];
void ini() {
for(int i = 1 ; i < N ; ++i) {
sort(all(val[i]));
val[i].resize(unique(all(val[i])) - val[i].begin());
bit[i].resize(val[i].size() + 5);
}
}
void add(int x,int y) {
for(; x > 0 ; x -= x & -x)
val[x].push_back(y);
}
void upd(int x,int y,int v) {
for(; x > 0 ; x -= x & -x) {
int p = upper_bound(all(val[x]),y) - val[x].begin();
for(; p > 0 ; p -= p & -p)
bit[x][p] += v;
}
}
int get(int x,int y) {
int ans = 0;
for(; x < N ; x += x & -x) {
int p = lower_bound(all(val[x]),y) - val[x].begin() + 1;
int K = bit[x].size();
for(; p < K ; p += p & -p)
ans += bit[x][p];
}
return ans;
}
};
struct Rect {
int l, r;
int u, d;
int idx;
} Sheet[N];
vector<int> g[N];
set<int> S[N];
int ans[N];
void dfs(int u) {
for(int v : g[u]) {
dfs(v);
if (S[u].size() < S[v].size())
S[u].swap(S[v]);
for(int x : S[v])
S[u].insert(x);
}
ans[u] = S[u].size();
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int m; cin >> m;
vector<int> row;
for(int i = 0 ; i < n ; ++i) {
cin >> Sheet[i].l >> Sheet[i].u;
cin >> Sheet[i].r >> Sheet[i].d;
Sheet[i].idx = i + 1;
Sheet[i].l--;
Sheet[i].u--;
row.push_back(Sheet[i].l);
row.push_back(Sheet[i].r);
}
sort(all(row)); row.erase(unique(all(row)),row.end());
for(int i = 0 ; i < n ; ++i) {
Sheet[i].l = upper_bound(all(row),Sheet[i].l) - row.begin();
Sheet[i].r = upper_bound(all(row),Sheet[i].r) - row.begin();
BIT2D::add(Sheet[i].l,Sheet[i].u);
BIT2D::add(Sheet[i].l,Sheet[i].d);
BIT2D::add(Sheet[i].r,Sheet[i].u);
BIT2D::add(Sheet[i].r,Sheet[i].d);
}
BIT2D::ini();
sort(Sheet,Sheet + n,[&](const Rect &a,const Rect &b) {
return a.l < b.l;
});
for(int i = 0 ; i < n ; ++i) {
int x = Sheet[i].idx;
int y = BIT2D::get(Sheet[i].r,Sheet[i].d);
g[y].push_back(x);
BIT2D::upd(Sheet[i].l,Sheet[i].u,x - y);
BIT2D::upd(Sheet[i].r,Sheet[i].d,x - y);
BIT2D::upd(Sheet[i].l,Sheet[i].d,y - x);
BIT2D::upd(Sheet[i].r,Sheet[i].u,y - x);
}
for(int i = 0 ; i < m ; ++i) {
int x; cin >> x;
int y; cin >> y;
int k; cin >> k;
S[BIT2D::get(lower_bound(all(row),x) - row.begin() + 1,y)].insert(k);
}
dfs(0);
for(int i = 1 ; i <= n ; ++i) cout << ans[i] << "\n";
}
/*
2 2
1 1 3 3
5 6 10 10
3 3 1
5 1 2
*/
# | 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... |