#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
#define _ << " _ " <<
using namespace std;
const int N = 1e5 + 7;
int m, n, gx, gy, tot, t;
int p[N], res[N], cnt[N], st[N], ft[N], ver[N], deg[N];
vector <int> col[N];
bool vis[N];
vector <int> vx, vy;
map <int, int> mx, my;
vector <int> adj[N];
int sz[N];
void getsz(int v, int p){
sz[v] = 1;
st[v] = ++t;
ver[t] = v;
for(auto u : adj[v])
if(u != p){
getsz(u, v);
sz[v] += sz[u];
}
ft[v] = t;
}
struct Rect{
int lx, ly, hx, hy, id;
Rect() {}
Rect(int lx, int ly, int hx, int hy): lx(lx), ly(ly), hx(hx), hy(hy) {}
}rect[N];
struct Shot{
int x, y, c;
Shot() {}
Shot(int x, int y, int c): x(x), y(y), c(c) {}
}shot[N];
struct Event{
int id, l, h;
Event() {}
Event(int id, int l, int h): id(id), l(l), h(h) {}
};
vector <Event> event[5 * N];
struct segTree{
int tree[N << 5];
int lazy[N << 5];
segTree(){
memset(lazy, -1, sizeof(lazy));
}
void Lazy(int x){
if (lazy[x] != -1){
tree[x] = lazy[x];
lazy[2 * x] = lazy[x];
lazy[2 * x + 1] = lazy[x];
lazy[x] = -1;
}
}
void Update(int x, int l, int r, int i, int j, int val){
Lazy(x);
if (l > j || r < i) return;
if (l >= i && r <= j) {
lazy[x] = val;
Lazy(x);
return;
}
int mid = l + r >> 1;
Update(2 * x, l, mid, i, j, val);
Update(2 * x + 1, mid + 1, r, i, j, val);
tree[x] = max(tree[2 * x], tree[2 * x + 1]);
}
int Query(int x, int l, int r, int i, int j){
Lazy(x);
if (l > j || r < i) return 0;
if (l >= i && r <= j) return tree[x];
int mid = l + r >> 1;
return max(Query(2 * x, l, mid, i, j), Query(2 * x + 1, mid + 1, r, i, j));
}
}IT;
inline void Compress(vector <int> v, map <int, int> &m, int &g){
sort(v.begin(), v.end());
m[v[0]] = ++g;
for (int i = 1; i < v.size(); i++)
if (v[i] != v[i - 1])
m[v[i]] = ++g;
}
inline void add(int c){
cnt[c]++;
if (cnt[c] == 1) tot++;
}
inline void del(int c){
cnt[c]--;
if (cnt[c] == 0) tot--;
}
void dfs(int v, int p, bool keep){
int mx = -1, bigChild = -1;
vis[v] = true;
for(auto u : adj[v])
if(u != p && sz[u] > mx)
mx = sz[u], bigChild = u;
for(auto u : adj[v])
if(u != p && u != bigChild)
dfs(u, v, 0);
if(bigChild != -1)
dfs(bigChild, v, 1);
for (int u: adj[v])
if (u != p && u != bigChild)
for (int x = st[u]; x <= ft[u]; x++){
int vertice = ver[x];
for (int c: col[vertice])
add(c);
}
for (int c: col[v])
add(c);
res[v] = tot;
if(keep == 0){
for (int x = st[v]; x <= ft[v]; x++){
int vertice = ver[x];
for (int c: col[vertice])
del(c);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++){
int lx, ly, hx, hy;
cin >> lx >> ly >> hx >> hy;
rect[i].id = i;
rect[i] = Rect(lx, ly, hx, hy);
vx.push_back(lx); vx.push_back(hx);
vy.push_back(ly); vy.push_back(hy);
}
for (int i = 1; i <= m; i++){
int x, y, c;
cin >> x >> y >> c;
shot[i] = Shot(x, y, c);
vx.push_back(x);
vy.push_back(y);
}
Compress(vx, mx, gx);
Compress(vy, my, gy);
for (int i = 1; i <= n; i++){
int lx = mx[rect[i].lx];
int ly = my[rect[i].ly];
int hx = mx[rect[i].hx];
int hy = my[rect[i].hy];
rect[i] = Rect(lx, ly, hx, hy);
event[lx].push_back(Event(i, ly, hy));
}
for (int i = 1; i <= m; i++){
int x = mx[shot[i].x];
int y = my[shot[i].y];
shot[i].x = x;
shot[i].y = y;
event[x].push_back(Event(N + shot[i].c, y, y));
}
for (int i = 1; i <= n; i++){
int lx = rect[i].lx;
int ly = rect[i].ly;
int hx = rect[i].hx;
int hy = rect[i].hy;
event[hx].push_back(Event(-i, ly, hy));
}
for (int i = 1; i <= gx; i++){
for (Event e: event[i]){
int id = e.id;
int l = e.l;
int h = e.h;
if (id > 0 && id < N){
int v = IT.Query(1, 1, gy, l, h);
if (v){
adj[v].push_back(id);
deg[id]++;
p[id] = v;
}
IT.Update(1, 1, gy, l, h, id);
}
if (id < 0){
IT.Update(1, 1, gy, l, h, p[-id]);
}
if (id > 0 && id > N){
int v = IT.Query(1, 1, gy, l, h);
col[v].push_back(id - N);
}
}
}
t = 0;
for (int i = 1; i <= n; i++){
if (deg[i] == 0 && !sz[i])
getsz(i, i);
}
for (int i = 1; i <= n; i++)
if (deg[i] == 0 && !vis[i]){
tot = 0;
dfs(i, -1, 0);
}
for (int i = 1; i <= n; i++)
cout << res[i] << endl;
}
Compilation message
plahte.cpp: In member function 'void segTree::Update(int, int, int, int, int, int)':
plahte.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
plahte.cpp: In member function 'int segTree::Query(int, int, int, int, int)':
plahte.cpp:87:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
plahte.cpp: In function 'void Compress(std::vector<int>, std::map<int, int>&, int&)':
plahte.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < v.size(); i++)
~~^~~~~~~~~~
plahte.cpp: In function 'void dfs(int, int, bool)':
plahte.cpp:122:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(bigChild != -1)
^~
plahte.cpp:125:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
for (int u: adj[v])
^~~
plahte.cpp: In function 'int main()':
plahte.cpp:194:7: warning: unused variable 'lx' [-Wunused-variable]
int lx = rect[i].lx;
^~
plahte.cpp:150:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:150:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
359 ms |
42428 KB |
Output is correct |
| 2 |
Correct |
287 ms |
41668 KB |
Output is correct |
| 3 |
Correct |
27 ms |
29304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
364 ms |
46360 KB |
Output is correct |
| 2 |
Correct |
355 ms |
46792 KB |
Output is correct |
| 3 |
Correct |
28 ms |
29436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
630 ms |
58960 KB |
Output is correct |
| 2 |
Correct |
640 ms |
56200 KB |
Output is correct |
| 3 |
Correct |
28 ms |
29432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1147 ms |
74708 KB |
Output is correct |
| 2 |
Correct |
1149 ms |
73396 KB |
Output is correct |
| 3 |
Correct |
27 ms |
29432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1124 ms |
73348 KB |
Output is correct |
| 2 |
Correct |
1036 ms |
70224 KB |
Output is correct |
| 3 |
Correct |
51 ms |
29432 KB |
Output is correct |
