/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 80100;
stack < pair < int, int > > tree[8 * maxn];
void update(int root, int left, int right, int qleft, int qright, int val, int tm)
{
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
if (val == -1)
tree[root].pop();
else
tree[root].push({tm, val});
return;
}
int mid = (left + right ) / 2;
update(root * 2, left, mid, qleft, qright, val, tm);
update(root * 2 + 1, mid + 1, right, qleft, qright, val, tm);
}
pair < int, int > query(int root, int left, int right, int pos)
{
pair < int, int > ans = {-1e9, -1};
if (!tree[root].empty())
ans = max(ans, tree[root].top());
if (left == right)
return ans;
int mid = (left + right) / 2;
if (pos <= mid)
ans = max(ans, query(root * 2, left, mid, pos));
else
ans = max(ans, query(root * 2 + 1, mid + 1, right, pos));
return ans;
}
struct point
{
int x, y;
void input()
{
cin >> x >> y;
}
};
struct rectangle
{
point A, B;
void input()
{
A.input();
B.input();
}
};
struct line
{
point cor;
int len, type, idx;
};
int n, m, col[maxn];
rectangle r[maxn];
point s[maxn];
void read_data()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
r[i].input();
for (int i = 1; i <= m; i ++)
s[i].input(), cin >> col[i];
}
int xcor, ycor;
void compress_data()
{
vector < int > dx, dy, dc;
for (int i = 1; i <= n; i ++)
{
dx.push_back(r[i].A.x);
dx.push_back(r[i].B.x);
dy.push_back(r[i].A.y);
dy.push_back(r[i].B.y);
}
for (int i = 1; i <= m; i ++)
{
dx.push_back(s[i].x);
dy.push_back(s[i].y);
dc.push_back(col[i]);
}
sort(dx.begin(), dx.end());
sort(dy.begin(), dy.end());
sort(dc.begin(), dc.end());
dx.erase(unique(dx.begin(), dx.end()), dx.end());
dy.erase(unique(dy.begin(), dy.end()), dy.end());
dc.erase(unique(dc.begin(), dc.end()), dc.end());
xcor = dx.size();
ycor = dy.size();
unordered_map < int, int > mx, my, mc;
for (int i = 0; i < dx.size(); i ++)
mx[dx[i]] = i + 1;
for (int i = 0; i < dy.size(); i ++)
my[dy[i]] = i + 1;
for (int i = 0; i < dc.size(); i ++)
mc[dc[i]] = i + 1;
for (int i = 1; i <= n; i ++)
{
r[i].A.x = mx[r[i].A.x];
r[i].A.y = my[r[i].A.y];
r[i].B.x = mx[r[i].B.x];
r[i].B.y = my[r[i].B.y];
}
for (int i = 1; i <= m; i ++)
{
s[i].x = mx[s[i].x];
s[i].y = my[s[i].y];
col[i] = mc[col[i]];
}
}
bool cmp(const line &l1, const line &l2)
{
if (l1.cor.x != l2.cor.x)
return l1.cor.x < l2.cor.x;
return l1.type > l2.type;
}
void creat_events(vector < line > &events)
{
for (int i = 1; i <= n; i ++)
{
line l;
l.cor.x = r[i].A.x;
l.cor.y = r[i].A.y;
l.idx = i;
l.len = r[i].B.y - r[i].A.y;
l.type = 1;
events.push_back(l);
l.cor.x = r[i].B.x;
l.type = -1;
events.push_back(l);
}
for (int i = 1; i <= m; i ++)
{
line l;
l.cor = s[i];
l.len = 0;
l.type = 0;
l.idx = i;
events.push_back(l);
}
sort(events.begin(), events.end(), cmp);
}
vector < int > adj[maxn];
int sub[maxn], deg[maxn];
vector < int > upd[maxn];
void sweep_line()
{
vector < line > events;
creat_events(events);
for (int i = 0; i < events.size(); i ++)
{
line cur = events[i];
///cout << "event " << i << " " << cur.type << " " << cur.cor.x << " " << cur.cor.y << " " << cur.cor.y + cur.len << endl;
if (cur.type == 1)
{
int par = query(1, 1, ycor, cur.cor.y).second;
if (par != -1)
adj[par].push_back(cur.idx), deg[cur.idx] ++;
update(1, 1, ycor, cur.cor.y, cur.cor.y + cur.len, cur.idx, i);
}
else if (cur.type == -1)
{
update(1, 1, ycor, cur.cor.y, cur.cor.y + cur.len, -1, -1);
}
else
{
int par = query(1, 1, ycor, cur.cor.y).second;
if (par != -1)
{
upd[par].push_back(col[cur.idx]);
}
///cout << "here " << par << endl;
}
}
}
int used[maxn], ans[maxn];
void calc(int v)
{
sub[v] = 1;
for (int u : adj[v])
{
calc(u);
sub[v] += sub[u];
}
}
unordered_set < int > st[maxn];
void dfs(int v)
{
int mx = -1;
for (int u : adj[v])
{
if (mx == -1 || sub[u] > sub[mx])
mx = u;
}
for (int u : adj[v])
{
dfs(u);
}
if (mx != -1)
swap(st[mx], st[v]);
for (int d : upd[v])
st[v].insert(d);
for (int u : adj[v])
{
if (u != mx)
for (int d : st[u])
st[v].insert(d);
}
ans[v] = st[v].size();
}
void traverse_graph()
{
for (int i = 1; i <= n; i ++)
if (deg[i] == 0)
adj[0].push_back(i);
calc(0);
dfs(0);
for (int i = 1; i <= n; i ++)
cout << ans[i] << endl;
}
void solve()
{
read_data();
compress_data();
sweep_line();
traverse_graph();
}
int main()
{
///freopen("test.txt", "r", stdin);
speed();
solve();
return 0;
}
Compilation message
plahte.cpp: In function 'void compress_data()':
plahte.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i = 0; i < dx.size(); i ++)
| ~~^~~~~~~~~~~
plahte.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (int i = 0; i < dy.size(); i ++)
| ~~^~~~~~~~~~~
plahte.cpp:135:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for (int i = 0; i < dc.size(); i ++)
| ~~^~~~~~~~~~~
plahte.cpp: In function 'void sweep_line()':
plahte.cpp:199:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | for (int i = 0; i < events.size(); i ++)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
309 ms |
447760 KB |
Output is correct |
| 2 |
Correct |
288 ms |
449096 KB |
Output is correct |
| 3 |
Correct |
198 ms |
439796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
326 ms |
450280 KB |
Output is correct |
| 2 |
Correct |
307 ms |
450440 KB |
Output is correct |
| 3 |
Correct |
211 ms |
439900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
389 ms |
455700 KB |
Output is correct |
| 2 |
Correct |
390 ms |
457608 KB |
Output is correct |
| 3 |
Correct |
200 ms |
439768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
547 ms |
465316 KB |
Output is correct |
| 2 |
Correct |
547 ms |
469580 KB |
Output is correct |
| 3 |
Correct |
206 ms |
439884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
534 ms |
465512 KB |
Output is correct |
| 2 |
Correct |
521 ms |
467944 KB |
Output is correct |
| 3 |
Correct |
206 ms |
439880 KB |
Output is correct |
