#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 = 2e5 + 7;
int m, n, gx, gy;
int p[N], res[N];
bool vis[N];
vector <int> vx, vy;
map <int, int> mx, my;
vector <int> adj[N];
set <int> Set[N];
int sz[N];
void getsz(int v, int p){
sz[v] = Set[v].size();
for(auto u : adj[v])
if(u != p){
getsz(u, v);
sz[v] += sz[u];
}
}
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[N];
struct segTree{
int tree[N << 3];
int lazy[N << 3];
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;
}
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;
// db(v _ bigChild _ mx);
for(auto u : adj[v])
if(u != p && u != bigChild)
dfs(u, v, 0);
if(bigChild != -1)
dfs(bigChild, v, 1);
// db(v _ adj[v].size());
// for(auto u : adj[v])
// if(u != p && u != bigChild){
// for (int x: Set[u]){
// Set[v].insert(x);
// }
// }
if (p > 0)
for (int x: Set[v])
Set[p].insert(x);
res[v] = Set[v].size();
if(keep == 0)
Set[v].clear();
}
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);
// db(id _ v _ l _ h);
if (v){
adj[id].push_back(v);
adj[v].push_back(id);
p[id] = v;
}
IT.Update(1, 1, gy, l, h, id);
}
if (id < 0){
// db(-id _ p[-id] _ l _ h);
IT.Update(1, 1, gy, l, h, p[-id]);
// for (int j = 1; j <= gy; j++)
// cerr << IT.Query(1, 1, gy, j, j) << ' ';
// cerr << endl;
}
if (id > 0 && id > N){
int v = IT.Query(1, 1, gy, l, h);
// db(v _ l _ h);
Set[v].insert(id - N);
}
}
}
// for (int i = 1; i <= n; i++){
// cout << i << " | ";
// for (int x: Set[i])
// cout << x << ' ';
// cout << endl;
// }
for (int i = 1; i <= n; i++)
if (!sz[i])
getsz(i, -1);
for (int i = 1; i <= n; i++)
if (!vis[i])
dfs(i, -1, 1);
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:74: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:84: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:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < v.size(); i++)
~~^~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:177:7: warning: unused variable 'lx' [-Wunused-variable]
int lx = rect[i].lx;
^~
plahte.cpp:132: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:132: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 |
Execution timed out |
2052 ms |
40252 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
44128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
57316 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
359 ms |
110108 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
351 ms |
110784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
