#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}
#define re return
#define ft first
#define sd second
#pragma GCC optimize("O3")
mt19937 rnd(chrono::system_clock().now().time_since_epoch().count());
int rint(int v) {re rnd() % v;}
const int N = 8e4 + 5;
int n, m, mxx, mxy, mxc;
vector<int> p;
vector<ll> area;
map<int, int> shrink_x, shrink_y, shrink_c;
struct rect {
int x, y, X, Y;
rect() {
cin >> x >> y >> X >> Y;
shrink_x[x], shrink_x[X];
shrink_y[y], shrink_y[Y];
}
void init(ll *a) {
x = shrink_x[x];
X = shrink_x[X];
y = shrink_y[y];
Y = shrink_y[Y];
(*a = X - x) *= (ll)Y - y;
}
};
vector<rect> rects;
struct ball {
int x, y, c;
ball() {
cin >> x >> y >> c;
shrink_x[x];
shrink_y[y];
shrink_c[c];
}
void init() {
x = shrink_x[x];
y = shrink_y[y];
c = shrink_c[c];
}
};
vector<ball> balls;
struct cmp {
bool operator() (const int &a, const int &b) const {
return area[a] == area[b]
? a < b
: area[a] < area[b];
}
};
int cur, upper_rect;
struct tree {
tree *l, *r;
set<int, cmp> v {}, f {};
tree(int tl = 0, int tr = mxy - 1): l(r = 0) {
if(tl < tr) {
int tm = (tl + tr) >> 1;
l = new tree(tl, tm);
r = new tree(tm + 1, tr);
}
}
void add(int ql, int qr, int tl = 0, int tr = mxy - 1) {
if(ql > qr) re;
if(!f.empty()) {
int u = *f.begin();
if(upper_rect < 0 || area[upper_rect] > area[u])
upper_rect = u;
}
if(ql == tl && qr == tr) {
f.insert(cur);
if(!v.empty()) {
int u = *v.begin();
if(upper_rect < 0 || area[upper_rect] > area[u])
upper_rect = u;
}
} else {
v.insert(cur);
int tm = (tl + tr) >> 1;
l->add(ql, min(qr, tm), tl, tm);
r->add(max(tm + 1, ql), qr, tm + 1, tr);
}
}
void del(int ql, int qr, int tl = 0, int tr = mxy - 1) {
if(ql > qr) re;
if(ql == tl && qr == tr) re void(f.erase(cur));
v.erase(cur);
if(tl < tr) {
int tm = (tl + tr) >> 1;
l->del(ql, min(qr, tm), tl, tm);
r->del(max(tm + 1, ql), qr, tm + 1, tr);
}
}
void shoot(int p, int tl = 0, int tr = mxy - 1) {
if(!f.empty()) {
int u = *f.begin();
if(cur < 0 || area[cur] > area[u])
cur = u;
}
if(tl == tr) re;
int tm = (tl + tr) >> 1;
p <= tm
? l->shoot(p, tl, tm)
: r->shoot(p, tm + 1, tr);
}
};
vector<int> g[N];
vector<int> nodes[N];
int l[N + N], r[N + N], timer, st[18][N + N], h[N], lg[N + N], rt[N], root;
void rec(int v, int he = 0) {
rt[v] = root, h[v] = he;
st[0][l[v] = r[v] = timer++] = v;
for(const int &u : g[v]) {
rec(u, he + 1);
st[0][r[v] = timer++] = v;
}
}
int mn(int a, int b) {re h[a] < h[b] ? a : b;}
void build_sparse() {
for(int i = 0; i < N + N; ++i) lg[i] = !i ? 0 : lg[i - 1] + (1 << lg[i - 1] + 1 <= i);
for(int j = 1; j < 18; ++j) for(int i = 0; i + (1 << j) - 1 < N + N; ++i)
st[j][i] = mn(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
}
int lca(int a, int b) {
if(l[a] > l[b]) swap(a, b);
if(r[a] >= r[b]) re a;
int f = lg[r[b] - l[a] + 1];
re mn(st[f][l[a]], st[f][r[b] - (1 << f) + 1]);
}
int z[N];
int count(int v) { for(int u : g[v]) z[v] += count(u); re z[v]; }
int main() {
#ifdef _LOCAL
freopen("10.in", "r", stdin);
freopen("10.out", "w", stdout);
#endif // _LOCAL
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 0; i < n; ++i) rects.emplace_back();
for(int i = 0; i < m; ++i) balls.emplace_back();
for(auto t : shrink_x) shrink_x[t.ft] = mxx++;
for(auto t : shrink_y) shrink_y[t.ft] = mxy++;
for(auto t : shrink_c) shrink_c[t.ft] = mxc++;
area.resize(n);
ll *pt_a = &area[0];
for(auto &t : rects) t.init(pt_a++);
for(auto &t : balls) t.init();
tree t {};
vector<int> rect_add(n);
for(int i = 0; i < n; ++i) rect_add[i] = i;
sort(rect_add.begin(), rect_add.end(),
[&] (const int &a, const int &b) {return rects[a].x != rects[b].x
? rects[a].x < rects[b].x
: area[a] > area[b];});
vector<int> rect_del = rect_add;
sort(rect_del.begin(), rect_del.end(),
[&] (const int &a, const int &b) {return rects[a].X < rects[b].X;});
vector<int> shot(m);
for(int i = 0; i < m; ++i) shot[i] = i;
sort(shot.begin(), shot.end(),
[&] (const int &a, const int &b) {return balls[a].x < balls[b].x;});
p.assign(n, -1);
int ai = 0, di = 0, si = 0;
for(int x = 0; x < mxx; ++x) {
for(; ai < n && rects[rect_add[ai]].x == x; ++ai) {
cur = rect_add[ai];
upper_rect = -1;
t.add(rects[cur].y, rects[cur].Y);
p[cur] = upper_rect;
// cerr << "add " << rects[cur].y << ' ' << rects[cur].Y << endl;
}
for(; si < m && balls[shot[si]].x == x; ++si) {
cur = -1;
t.shoot(balls[shot[si]].y);
if(~cur) nodes[balls[shot[si]].c].push_back(cur);
// cerr << "shoot " << balls[shot[si]].c << ' ' << balls[shot[si]].y << endl;
}
for(; di < n && rects[rect_del[di]].X == x; ++di) {
cur = rect_del[di];
t.del(rects[cur].y, rects[cur].Y);
// cerr << "del " << rects[cur].y << ' ' << rects[cur].Y << endl;
}
}
for(int i = 0; i < n; ++i) if(~p[i]) g[p[i]].push_back(i);
for(int i = 0; i < n; ++i) if(p[i] < 0) root = i, rec(i);
build_sparse();
for(int c = 0; c < mxc; c++) {
vector<int> &ns = nodes[c];
sort(ns.begin(), ns.end(), [&] (const int &a, const int &b) {return l[a] < l[b];});
int v = -1;
for(int i : ns) v < 0 || rt[v] != rt[i]
? z[v = i]++
: (z[i]++, z[lca(i, v)]--, v = i);
}
for(int i = 0; i < n; ++i) if(p[i] < 0) count(i);
for(int i = 0; i < n; ++i) cout << z[i] << '\n';
}
Compilation message
plahte.cpp: In function 'void build_sparse()':
plahte.cpp:145:81: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
for(int i = 0; i < N + N; ++i) lg[i] = !i ? 0 : lg[i - 1] + (1 << lg[i - 1] + 1 <= i);
~~~~~~~~~~^~~
plahte.cpp:147:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
st[j][i] = mn(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
407 ms |
49620 KB |
Output is correct |
| 2 |
Correct |
359 ms |
42220 KB |
Output is correct |
| 3 |
Correct |
15 ms |
14464 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
606 ms |
84020 KB |
Output is correct |
| 2 |
Correct |
570 ms |
63540 KB |
Output is correct |
| 3 |
Correct |
15 ms |
14464 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1220 ms |
147172 KB |
Output is correct |
| 2 |
Correct |
973 ms |
82008 KB |
Output is correct |
| 3 |
Correct |
15 ms |
14464 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2092 ms |
230148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2063 ms |
205296 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
