/******************************
* author : @yayayaya *
* date : 21 / 10 / 2022 *
******************************/
/* (≈ㅇᆽㅇ≈)♡ (≈ㅇᆽㅇ≈)♡ (≈ㅇᆽㅇ≈)♡ (≈ㅇᆽㅇ≈)♡ (≈ㅇᆽㅇ≈)♡ */
/*
/^--^\ /^--^\ /^--^\
\____/ \____/ \____/
/ \ / \ / \
| | | | | |
\__ __/ \__ __/ \__ __/
|^|^|^|^|^|^|^|^|^|^|^|^\ \^|^|^|^/ /^|^|^|^|^\ \^|^|^|^|^|^|^|^|^|^|^|^|
| | | | | | | | | | | | |\ \| | |/ /| | | | | |\ \| | | | | | | | | | | |
| | | | | | | | | | | | |/ /| | |\ \| | | | | |/ /| | | | | | | | | | | |
| | | | | | | | | | | | |\/ | | | \/| | | | | |\/ | | | | | | | | | | | |
#########################################################################
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | */
/*******************************************************************************************
* ################################################################# *
* # _` # *
* # _ooOoo_ # *
* # o8888888o # *
* # 88" . "88 # *
* # (| -_- |) # *
* # O\ = /O # *
* # ____/`---'\____ # *
* # .' \| |// `. # *
* # / \||| : |||// \ # *
* # / _||||| -:- |||||_ \ # *
* # | | \ - /'| | | # *
* # | \_| `\`---'// |_/ | # *
* # \ .-\__ `-. -'__/-. / # *
* # ___`. .' /--.--\ `. .'___ # *
* # ."" '< `.___\_<|>_/___.' _> \"". # *
* # | | : `- \`. ;`. _/; .'/ / .' ; | # *
* # \ \ `-. \_\_`. _.'_/_/ -' _.' / # *
* #=============`-.`___`-.__\ \___ /__.-'_.'_.-'=================# *
* `=--=-' *
* *
* /\_/\* *
* ( -.-) *
* _.-/`) / >O \>1 _.-/`) *
* // / / ) // / / ) *
* .=// / / / ) /\_/\ /\_/\ .=// / / / ) *
* //`/ / / / / ( -.-) ( -.-) //`/ / / / / *
* // / ` / / >O \>1 / >O \>1 // / ` / *
* \ / \ / *
* )) .' /\_/\ /\_/\ /\_/\ )) .' *
* // / ( -.-) ( -.-) ( -.-) // / *
* / / >O \>1 / >O \>1 / >O \>1 / *
* *
*******************************************************************************************/
#include <bits/stdc++.h>
// #pragma GCC optimize("O2")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize ("O3,unroll-loops,no-stack-protector")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define PB push_back
#define ALL(i_) i_.begin(), i_.end()
#define LOG2(x) (31 - __builtin_clz(x))
#define getBit(x, i) ((x >> i) & 1)
#define rd(l, r) (l + rng() % (r - l + 1))
#define FOR(i_, a_, b_) for(int i_ = (int) (a_); i_ <= (int) (b_); ++i_)
#define FORD(i_, a_, b_) for(int i_ = (int) (a_); i_ >= (int) (b_); --i_)
#define db(val) "["#val" = "<<(val)<<"] "
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
template<class X, class Y> bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {
x = y;
return 1;
}
return 0;
}
template<class X, class Y> bool maximize(X &x, const Y &y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return 1;
}
return 0;
}
template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); }
const int mod = (int) 1e9 + 7;
const int oo = (int) 1e9 + 99;
const int LOG = (int) 20;
const ii dxy8[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1}, {1, -1}, {1, 1}, {-1, 1}, {-1, -1} };
const ii dxy4[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
const int maxn = (int) 1e5 + 1;
int n, m;
vector<array<int, 3>> event;
vector<int> X1, X2, X3, color, par, res;
set<array<int, 3>> se;
vector<set<int>> co;
vector<vector<int>> adj;
int getPar(int pos){
array<int, 3> cur = {pos, 0, 0};
auto it = se.lower_bound(cur);
if(it == se.end()) return 0;
if((*it)[1] == -1) return par[(*it)[2]];
return (*it)[2];
}
int cnt;
vector<int> toNode, tin, tout;
void getSize(int u = 0, int par = -1){
toNode[++cnt] = u;
tin[u] = cnt;
for(int v : adj[u]) if(v != par) getSize(v, u);
tout[u] = cnt;
}
set<int> cur;
#define sz(x) (tout[x] - tin[x] + 1)
void DFS(int u = 0, int par = -1, bool isClear = 0){
int bigChild = -1;
for(int v : adj[u]) if(v != par){
if((bigChild == -1) || (sz(v) > sz(bigChild))) bigChild = v;
}
for(int v : adj[u]) if(v != par && v != bigChild) DFS(v, u, 1);
if(bigChild != -1) DFS(bigChild, u, 0);
for(int v : adj[u]) if(v != par && v != bigChild){
for(int p = tin[v]; p <= tout[v]; p++){
int x = toNode[p];
for(auto c : co[x]) cur.insert(c);
}
}
for(auto c : co[u]) cur.insert(c);
res[u] = (int) cur.size();
if(isClear){
cur.clear();
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define TASK "PLAHTE"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
cin >> n >> m;
X1.resize(n + 1, 0);
X2.resize(n + 1, 0);
FOR(i, 1, n){
int x1, x2; cin >> x1 >> X1[i] >> x2 >> X2[i];
event.PB({x1, -1, i});
event.PB({x2, 1, i});
}
X3.resize(m + 1, 0);
color.resize(m + 1, 0);
FOR(i, 1, m){
int x;
cin >> x >> X3[i] >> color[i];
event.PB({x, 0, i});
}
sort(ALL(event));
par.resize(n + 1, 0);
co.resize(n + 1, {});
for(auto x : event){
if(x[1] == -1){
par[x[2]] = getPar(X1[x[2]]);
se.insert({X1[x[2]], -1, x[2]});
se.insert({X2[x[2]], 1, x[2]});
}
else if(x[1] == 0){
co[getPar(X3[x[2]])].insert(color[x[2]]);
}
else{
se.erase({X1[x[2]], -1, x[2]});
se.erase({X2[x[2]], 1, x[2]});
}
}
adj.resize(n + 1);
FOR(i, 1, n){
adj[i].PB(par[i]);
adj[par[i]].PB(i);
}
res.resize(n + 1, 0);
toNode.resize(n + 1, 0);
tin.resize(n + 1, 0);
tout.resize(n + 1, 0);
getSize();
DFS();
FOR(i, 1, n) cout << res[i] << "\n";
return 0;
}
/// CONCACOCONCACOCONCACOCONCACOCONCACOCONCACOCONCACOCONCACOCONCACO ///
Compilation message
plahte.cpp: In function 'int main()':
plahte.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
159 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
67 ms |
7736 KB |
Output is correct |
| 2 |
Correct |
67 ms |
7632 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
81 ms |
11336 KB |
Output is correct |
| 2 |
Correct |
88 ms |
9724 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
148 ms |
20652 KB |
Output is correct |
| 2 |
Correct |
136 ms |
15456 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
244 ms |
32552 KB |
Output is correct |
| 2 |
Correct |
247 ms |
23616 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
233 ms |
29724 KB |
Output is correct |
| 2 |
Correct |
223 ms |
24340 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
