#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 <ll, ll>;
using pil = pair <ll, ll>;
using pli = pair <ll, ll>;
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 ll maxN = 1e5 + 1;
const ll inf = 0x3f3f3f3f;
ll n, m;
struct TRect{
ll x, y, u, v;
};
TRect a[maxN];
vector <ll> node;
struct TNode{
ll lazy, val;
TNode() : lazy(-1), val(0){}
};
TNode st[maxN * 16];
void pull(ll 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(ll id, ll i, ll j, ll val, ll l = 1, ll 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);
ll mid = (l + r) / 2;
update(id * 2, i, j, val, l, mid);
update(id * 2 + 1, i, j, val, mid + 1, r);
}
ll get(ll id, ll i, ll l = 1, ll r = node.size()){
if (r < i || l > i) return 0;
if (l == r) return st[id].val;
pull(id);
ll mid = (l + r) / 2;
return get(id * 2, i, l, mid) | get(id * 2 + 1, i, mid + 1, r);
}
vector <ll> adj[maxN];
set <ll> color[maxN];
ll par[maxN];
ll ans[maxN];
void dfs(ll u){
for (ll i: adj[u]){
dfs(i);
if (color[u].size() < color[i].size()) swap(color[u], color[i]);
for (ll j: color[i]) color[u].insert(j);
}
ans[u] = color[u].size();
}
struct TQuery{
ll x, y, v, idx, t;
};
vector <TQuery> q;
void Init(){
cin >> n >> m;
for (ll 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);
for (ll i = 1; i <= m; ++i){
ll x, y, z;
cin >> x >> y >> z;
q.pb({x, y, z, i, 1});
node.pb(y);
}
sort(node.begin(), node.end());
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){
ll low = upper_bound(node.begin(), node.end(), i.y) - node.begin();
ll high = upper_bound(node.begin(), node.end(), i.v) - node.begin();
update(1, low, high, par[i.idx]);
}
if (!i.t){
ll low = upper_bound(node.begin(), node.end(), i.y) - node.begin();
ll high = upper_bound(node.begin(), node.end(), i.v) - node.begin();
ll k = get(1, low);
adj[k].pb(i.idx);
par[i.idx] = k;
update(1, low, high, i.idx);
}
if (i.t == 1){
ll low = upper_bound(node.begin(), node.end(), i.y) - node.begin();
ll k = get(1, low);
color[k].insert(i.v);
}
}
color[0].clear();
dfs(0);
for (ll i = 1; i <= n; ++i) cout << ans[i] << "\n";
}
signed 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 |
97 ms |
40080 KB |
Output is correct |
| 2 |
Correct |
95 ms |
40732 KB |
Output is correct |
| 3 |
Correct |
20 ms |
32340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
42236 KB |
Output is correct |
| 2 |
Correct |
119 ms |
41672 KB |
Output is correct |
| 3 |
Correct |
15 ms |
32340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
50136 KB |
Output is correct |
| 2 |
Correct |
184 ms |
50084 KB |
Output is correct |
| 3 |
Correct |
16 ms |
32340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
330 ms |
60412 KB |
Output is correct |
| 2 |
Correct |
310 ms |
60820 KB |
Output is correct |
| 3 |
Correct |
15 ms |
32420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
292 ms |
58360 KB |
Output is correct |
| 2 |
Correct |
342 ms |
60664 KB |
Output is correct |
| 3 |
Correct |
15 ms |
32416 KB |
Output is correct |
