/**
____ ____ ____ ____ ____ ____
||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);
}
struct node
{
stack < pair < int, int > > st;
};
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;
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);
}
sort(dx.begin(), dx.end());
sort(dy.begin(), dy.end());
dx.erase(unique(dx.begin(), dx.end()), dx.end());
dy.erase(unique(dy.begin(), dy.end()), dy.end());
xcor = dx.size();
ycor = dy.size();
unordered_map < int, int > mx, my;
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 = 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];
}
}
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];
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);
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)
sub[par] ++;
///cout << "here " << par << endl;
}
}
}
int used[maxn];
void dfs(int v)
{
used[v] = 1;
for (int u : adj[v])
{
if (used[u])
continue;
dfs(u);
sub[v] += sub[u];
}
}
void traverse_graph()
{
for (int i = 1; i <= n; i ++)
if (!used[i])
dfs(i);
for (int i = 1; i <= n; i ++)
cout << sub[i] << endl;
}
void solve()
{
read_data();
compress_data();
sweep_line();
traverse_graph();
}
int main()
{
solve();
return 0;
}
Compilation message
plahte.cpp: In function 'void compress_data()':
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 < dx.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 < dy.size(); i ++)
| ~~^~~~~~~~~~~
plahte.cpp: In function 'void sweep_line()':
plahte.cpp:196:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for (int i = 0; i < events.size(); i ++)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
321 ms |
442160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
354 ms |
445540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
432 ms |
450804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
621 ms |
462096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
636 ms |
462336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
