#include <bits/stdc++.h>
#define pb push_back
#define rbg(v) v.rbegin()
#define bg(v) v.begin()
#define all(v) bg(v), v.end()
#define SZ(v) int(v.size())
#define MP make_pair
#define fi first
#define se second
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) forn(i, 0, n - 1)
#define for1(i, n) forn(i, 1, n)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define far0(i, n) fora(i, n - 1, 0)
#define far1(i, n) fora(i, n, 1)
#define foru(i, v) for(auto & i : v)
#define lb lower_bound
#define ub upper_bound
#define ord1(s, n) s + 1, s + int(n) + 1
#define ord0(s, n) s, s + int(n)
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
///#include <bits/extc++.h>
///using namespace __gnu_pbds;
///typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef long double ld;
typedef double db;
typedef __int128 Int;
const int mod = 1e9 + 7;
const int mod2 = 998244353;
///const int inf = 1e4;
const int MX = 8e4;
struct point{
int x, y;
point() : x(0), y(0) {}
point(int x, int y) : x(x), y(y) {}
};
istream &operator>>(istream &is, point & p){return is >> p.x >> p.y;}
ostream &operator<<(ostream &os, const point & p){return os << "(" << p.x << ", " << p.y << ")";}
struct rectangle{
point llc, urc;
rectangle() : llc(), urc() {}
rectangle(point llc, point urc) : llc(llc), urc(urc) {}
};
int p[MX];
vi tree[MX];
int st[12 * MX + 4];
bool lazy[12 * MX + 4];
int ans[MX];
vi shot[MX];
vector<rectangle> sheets;
vector<point> balls;
vi colour;
void build(int node, int l, int r){
st[node] = -1;
lazy[node] = 0;
if(l == r) return;
int m = (l + r) / 2;
build(node * 2, l, m);
build(node * 2 + 1, m + 1, r);
}
void push(int node, int l, int r){
if(l == r) return;
if(!lazy[node]) return;
st[node * 2] = st[node];
st[node * 2 + 1] = st[node];
lazy[node * 2] = 1;
lazy[node * 2 + 1] = 1;
st[node] = -1;
lazy[node] = 0;
}
int query(int node, int l, int r, int p){
push(node, l, r);
if(l == r) return st[node];
int m = (l + r) / 2;
if(p <= m) return query(node * 2, l, m, p);
return query(node * 2 + 1, m + 1, r, p);
}
void update(int node, int l, int r, int a, int b, int val){
push(node, l, r);
if(l > b || r < a) return;
if(a <= l && r <= b){
if(l == r){
st[node] = val;
return;
}
st[node * 2] = val;
st[node * 2 + 1] = val;
lazy[node * 2] = 1;
lazy[node * 2 + 1] = 1;
return;
}
int m = (l + r) / 2;
update(node * 2, l, m, a, b, val);
update(node * 2 + 1, m + 1, r, a, b, val);
}
struct ure{
int x, t, id;
const bool operator < (const ure & b) const {
if(x == b.x)
return t < b.t;
return x < b.x;
}
};
set<int> *cnt[MX];
void dfs(int u){
int mx = -1, bigchild = -1;
for(auto v : tree[u]){
dfs(v);
if(SZ((*cnt[v])) > mx){
mx = SZ((*cnt[v]));
bigchild = v;
}
}
cnt[u] = (bigchild == -1) ? new set<int>() : cnt[bigchild];
foru(c, shot[u]) (*cnt[u]).insert(c);
for(auto v : tree[u]){
if(v == bigchild) continue;
for(auto x : (*cnt[v]))
(*cnt[u]).insert(x);
}
ans[u] = SZ((*cnt[u]));
}
void solve(){
map<int, int> mp;
int n, m;
cin >> n >> m;
sheets.resize(n);
balls.resize(m);
colour.resize(m);
for0(i, n){
cin >> sheets[i].llc >> sheets[i].urc;
mp[sheets[i].llc.y] = 1;
mp[sheets[i].urc.y] = 1;
}
for0(i, m){
cin >> balls[i] >> colour[i];
mp[balls[i].y] = 1;
}
int id = 0;
for(auto & [key, val] : mp)
val = ++ id;
vector<ure> event;
for0(i, n){
sheets[i].llc.y = mp[sheets[i].llc.y];
sheets[i].urc.y = mp[sheets[i].urc.y];
event.pb({sheets[i].llc.x, 0, i});
event.pb({sheets[i].urc.x, 2, i});
}
for0(i, m){
balls[i].y = mp[balls[i].y];
event.pb({balls[i].x, 1, i});
}
sort(all(event));
build(1, 1, id);
int idx, t, aux;
int len = SZ(event);
for0(i, len){
idx = event[i].id;
t = event[i].t;
if(!t){
p[idx] = query(1, 1, id, sheets[idx].llc.y);
if(p[idx] != -1) tree[p[idx]].pb(idx);
update(1, 1, id, sheets[idx].llc.y, sheets[idx].urc.y, idx);
continue;
}
if(t == 1){
aux = query(1, 1, id, balls[idx].y);
if(aux != -1)
shot[aux].pb(colour[idx]);
continue;
}
update(1, 1, id, sheets[idx].llc.y, sheets[idx].urc.y, p[idx]);
}
for0(u, n)
if(p[u] == -1)
dfs(u);
for0(u, n)
cout << ans[u] << '\n';
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
///freopen("squares.in", "r", stdin);
///freopen("squares.out", "w", stdout);
int t = 1;
///cin >> t;
for1(i, t){
///cout << "Case " << i << ": ";
solve();
///cout << '\n';
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
61 ms |
19564 KB |
Output is correct |
| 2 |
Correct |
64 ms |
20428 KB |
Output is correct |
| 3 |
Correct |
1 ms |
7516 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
78 ms |
21664 KB |
Output is correct |
| 2 |
Correct |
78 ms |
21676 KB |
Output is correct |
| 3 |
Correct |
1 ms |
7516 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
144 ms |
30884 KB |
Output is correct |
| 2 |
Correct |
130 ms |
28604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
7512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
226 ms |
43204 KB |
Output is correct |
| 2 |
Correct |
239 ms |
39448 KB |
Output is correct |
| 3 |
Correct |
1 ms |
7512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
241 ms |
41668 KB |
Output is correct |
| 2 |
Correct |
250 ms |
39504 KB |
Output is correct |
| 3 |
Correct |
1 ms |
7516 KB |
Output is correct |
