#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>
using u32 = unsigned;
using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
using namespace std;
using pt = complex<f80>;
#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;
set<pair<int, int>> fw[N];
void input_c()
{
cin >> n >> m;
vector<int> cord_x, cord_y;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < 4; ++j) cin >> a[i][j];
cord_x.push_back(a[i][0]);
cord_x.push_back(a[i][2]);
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_x.push_back(b[i][0]);
cord_y.push_back(b[i][1]);
}
return;
sort(ALL(cord_x));
sort(ALL(cord_y));
for (int i = 0; i < n; ++i)
{
a[i][0] = lower_bound(ALL(cord_x), a[i][0]) - cord_x.begin() + 1;
a[i][2] = lower_bound(ALL(cord_x), a[i][2]) - cord_x.begin() + 1;
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][0] = lower_bound(ALL(cord_x), b[i][0]) - cord_x.begin() + 1;
b[i][1] = lower_bound(ALL(cord_y), b[i][1]) - cord_y.begin() + 1;
}
}
int par[N], parball[N];
set<pair<int, int>> nfw;
void ins(int i)
{
nfw.insert({a[i][3], i});
return;
for (int p = a[i][1]; p < N; p += p&-p)
fw[p].insert({a[i][3], i});
}
void del(int i)
{
nfw.erase({a[i][3], i});
return;
for (int p = a[i][1]; p < N; p += p&-p)
fw[p].erase({a[i][3], i});
}
int qry(int down_brder, int up_brder)
{
pair<int, int> z { 1000000, -1 };
auto it = nfw.lower_bound({up_brder, -1});
if (it != nfw.end() and a[it->second][1] <= down_brder) z = min(z, *it);
return z.second;
for (int p = down_brder; p; p -= p&-p)
{
auto it = fw[p].lower_bound({up_brder, -1});
if (it != fw[p].end()) z = min(z, *it);
}
return z.second;
}
set<int> st[N];
basic_string<int> g[N];
int vis[N], ans[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], i, -3);
ev_x.emplace_back(a[i][2], i, -1);
}
for (int i = 0; i < m; ++i)
{
ev_x.emplace_back(b[i][0], i, -2);
}
sort(ALL(ev_x));
for (auto [x, id, ty] : ev_x)
{
if (ty == -1)
{
par[id] = qry(a[id][1] - 1, a[id][3] + 1);
if (par[id] + 1) g[par[id]].push_back(id);
del(id);
}
else if (ty == -3)
{
ins(id);
}
else
{
parball[id] = qry(b[id][1], 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 |
Incorrect |
47 ms |
74100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
74564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
76300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
78420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
104 ms |
78152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
