#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,tune=native")
using namespace std;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 500005
int n, m;
array<int, 4> a[N];
array<int, 3> b[N];
vector<tuple<int, int, int>> ev_x;
void input_c()
{
cin >> n >> m;
vector<int> cord_y;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < 4; ++j) cin >> a[i][j];
cord_y.push_back(a[i][1]);
cord_y.push_back(a[i][3]);
}
for (int i = 0; i < m; ++i)
{
cin >> b[i][0] >> b[i][1] >> b[i][2];
cord_y.push_back(b[i][1]);
}
sort(ALL(cord_y));
for (int i = 0; i < n; ++i)
{
a[i][1] = lower_bound(ALL(cord_y), a[i][1]) - cord_y.begin() + 1;
a[i][3] = lower_bound(ALL(cord_y), a[i][3]) - cord_y.begin() + 1;
}
for (int i = 0; i < m; ++i)
{
b[i][1] = lower_bound(ALL(cord_y), b[i][1]) - cord_y.begin() + 1;
}
}
int par[N], parball[N];
int lz[N<<2], t[N<<2];
void push(int v, int l, int r)
{
if (lz[v] != -86)
{
if (l != r) lz[2*v+1] = lz[2*v+2] = lz[v];
t[v] = lz[v];
lz[v] = -86;
}
}
void upd(int v, int l, int r, int x, int y, int k)
{
push(v, l, r);
if (r < x||y<l)return;
if(x<=l&&r<=y){lz[v]=k;push(v,l,r);return;}
upd(2*v+1, l,(l+r)/2,x,y,k),upd(2*v+2,(l+r)/2+1,r,x,y,k);
}
int qry(int v,int l,int r,int p)
{
push(v,l,r);
if (l==r)return t[v];
if(p<=(l+r)/2)return qry(2*v+1,l,(l+r)/2,p);
return qry(2*v+2, (l+r)/2+1, r, p);
}
set<int> st[N];
basic_string<int> g[N];
int vis[N], ans[N], _prev[N];
void dfs(int u)
{
if (vis[u]) return;
vis[u] = 1;
for (auto v : g[u])
{
dfs(v);
if (st[v].size() > st[u].size()) st[v].swap(st[u]);
for (auto x : st[v]) st[u].insert(x);
}
ans[u] = st[u].size();
}
int main()
{
ShinLena;
input_c();
for (int i = 0; i < n; ++i)
ev_x.emplace_back(a[i][0], -3, i),
ev_x.emplace_back(a[i][2], -1, i);
for (int i = 0; i < m; ++i) ev_x.emplace_back(b[i][0], -2, i);
sort(ALL(ev_x));
upd(0, 1, N, 1, N, -1);
for (auto [x, ty, id] : ev_x)
{
if (ty == -1)
{
upd(0, 1, N, a[id][1], a[id][3], par[id]);
}
else if (ty == -3)
{
par[id] = qry(0, 1, N, a[id][1]);
if (par[id] + 1)
g[par[id]].push_back(id);
upd(0, 1, N, a[id][1], a[id][3], id);
}
else
{
parball[id] = qry(0, 1, N, b[id][1]);
if (parball[id] != -1)
st[parball[id]].insert(b[id][2]);
}
}
for (int i = 0; i < n; ++i) dfs(i), cout << ans[i] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
61504 KB |
Output is correct |
2 |
Correct |
83 ms |
62360 KB |
Output is correct |
3 |
Correct |
13 ms |
55900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
62304 KB |
Output is correct |
2 |
Correct |
90 ms |
62080 KB |
Output is correct |
3 |
Correct |
12 ms |
55900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
142 ms |
65500 KB |
Output is correct |
2 |
Correct |
141 ms |
64892 KB |
Output is correct |
3 |
Correct |
13 ms |
55900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
241 ms |
73584 KB |
Output is correct |
2 |
Correct |
256 ms |
70740 KB |
Output is correct |
3 |
Correct |
13 ms |
55896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
72204 KB |
Output is correct |
2 |
Correct |
222 ms |
70796 KB |
Output is correct |
3 |
Correct |
12 ms |
55728 KB |
Output is correct |