#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 1;
const int inf = 0x3f3f3f3f;
int n, m;
struct TRect{
int x, y, u, v;
};
TRect a[maxN];
vector <int> node;
struct TNode{
int lazy, val;
TNode() : lazy(-1), val(0){}
};
TNode st[maxN * 8];
void pull(int id){
if (st[id].lazy != -1){
st[id * 2].lazy = st[id * 2 + 1].lazy = st[id].lazy;
st[id * 2].val = st[id * 2 + 1].val = st[id].lazy;
st[id].lazy = -1;
}
}
void update(int id, int i, int j, int val, int l = 1, int r = node.size()){
if (r < i || l > j) return;
if (i <= l && r <= j){
st[id].val = val;
st[id].lazy = val;
return;
}
pull(id);
int mid = (l + r) / 2;
update(id * 2, i, j, val, l, mid);
update(id * 2 + 1, i, j, val, mid + 1, r);
}
int get(int id, int i, int l = 1, int r = node.size()){
if (r < i || l > i) return 0;
if (l == r) return st[id].val;
pull(id);
int mid = (l + r) / 2;
return get(id * 2, i, l, mid) | get(id * 2 + 1, i, mid + 1, r);
}
vector <int> adj[maxN];
set <int> color[maxN];
int par[maxN];
int ans[maxN];
void dfs(int u){
for (int i: adj[u]){
dfs(i);
if (color[u].size() < color[i].size()) swap(color[u], color[i]);
for (int j: color[i]) color[u].insert(j);
}
ans[u] = color[u].size();
}
struct TQuery{
int x, y, v, idx, t;
};
vector <TQuery> q;
void Init(){
cin >> n >> m;
for (int i = 1; i <= n; ++i){
cin >> a[i].x >> a[i].y >> a[i].u >> a[i].v;
q.pb({a[i].x, a[i].y, a[i].v, i, 0});
q.pb({a[i].u, a[i].y, a[i].v, i, 2});
node.pb(a[i].y);
node.pb(a[i].v);
}
node.pb(0); node.pb(inf);
sort(node.begin(), node.end());
for (int i = 1; i <= m; ++i){
int x, y, z;
cin >> x >> y >> z;
q.pb({x, y, z, i, 1});
}
sort(q.begin(), q.end(),[](const auto &i, const auto &j){
if (i.x == j.x){
return i.t < j.t;
}
return i.x < j.x;
});
for (auto i : q){
if (i.t == 2){
int low = upper_bound(node.begin(), node.end(), i.y) - node.begin();
int high = upper_bound(node.begin(), node.end(), i.v) - node.begin();
update(1, low, high, par[i.idx]);
}
if (!i.t){
int low = upper_bound(node.begin(), node.end(), i.y) - node.begin();
int high = upper_bound(node.begin(), node.end(), i.v) - node.begin();
int k = get(1, low);
adj[k].pb(i.idx);
par[i.idx] = k;
update(1, low, high, i.idx);
}
if (i.t == 1){
int low = upper_bound(node.begin(), node.end(), i.y) - node.begin();
int k = get(1, low);
color[k].insert(i.v);
}
}
color[0].clear();
dfs(0);
for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
}
int main(){
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
//freopen(taskname".out", "w", stdout);
}
faster;
ll tt = 1;
//cin >> tt;
while (tt--){
Init();
}
}
Compilation message
plahte.cpp: In function 'int main()':
plahte.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
143 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
18648 KB |
Output is correct |
| 2 |
Correct |
78 ms |
19392 KB |
Output is correct |
| 3 |
Correct |
7 ms |
13728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
20312 KB |
Output is correct |
| 2 |
Incorrect |
97 ms |
19564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
169 ms |
26116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
247 ms |
33472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
242 ms |
31556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
