| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1069571 |
2024-08-22T06:09:53 Z |
Perl32 |
Plahte (COCI17_plahte) |
C++17 |
|
541 ms |
79044 KB |
//I wrote this code 4 u <3
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
struct Info {
int v = -1;
Info() = default;
Info(int v) : v(v) {}
};
Info operator+(const Info &a, const Info &b) {
Info ret;
return ret;
}
struct Tag {
bool st = false;
int add = -1;
Tag() = default;
explicit Tag(int v) {
st = true;
add = v;
}
};
void apply(Info &a, Tag b) {
if (b.st) {
a.v = b.add;
}
}
void apply(Tag &a, Tag b) {
if (b.st) a = b;
}
template<class Info, class Tag, class Merge = plus<Info>>
class LazySegTree {
public:
int sz;
const Merge merge;
vector<Info> t;
vector<Tag> tag;
LazySegTree() = default;
LazySegTree(int n, const Info &v = Info()) : merge(Merge()) {
sz = 1;
while (sz < n) sz <<= 1;
t.assign(sz << 1, Info());
tag.assign(sz << 1, {});
for (int i = 0; i < n; ++i) {
t[i + sz] = v;
}
for (int i = sz - 1; i > 0; --i) {
pull(i);
}
}
LazySegTree(const vector<Info> &a) : merge(Merge()) {
sz = 1;
while (sz < szof(a)) sz <<= 1;
t.resize(sz << 1), tag.assign(sz << 1, {});
for (int i = 0; i < int(a.size()); ++i) {
t[i + sz] = a[i];
}
for (int i = sz - 1; i > 0; --i) {
pull(i);
}
}
void pull(int x) {
t[x] = merge(t[x << 1], t[x << 1 | 1]);
}
void apply(int p, const Tag &v) {
::apply(t[p], v);
::apply(tag[p], v);
}
void push(int x) {
apply(x << 1, tag[x]);
apply(x << 1 | 1, tag[x]);
tag[x] = Tag();
}
void modify(int i, const Info v, int x, int lx, int rx) {
if (rx - lx == 1) {
t[x] = v;
return;
}
int m = (lx + rx) >> 1;
push(x);
if (i < m) {
modify(i, v, x << 1, lx, m);
} else {
modify(i, v, x << 1 | 1, m, rx);
}
pull(x);
}
void modify(int p, const Info v) {
modify(p, v, 1, 0, sz);
}
Info query(int i, int x, int lx, int rx) {
if (lx + 1 == rx) return t[x];
int m = (lx + rx) >> 1;
push(x);
if (i < m) return query(i, x << 1, lx, m);
return query(i, x << 1 | 1, m, rx);
}
Info query(int i) {
return query(i, 1, 0, sz);
}
Info rangeQuery(int l, int r, int x, int lx, int rx) {
if (l >= rx || lx >= r) {
return Info();
}
if (l <= lx && rx <= r) {
return t[x];
}
int m = (lx + rx) >> 1;
push(x);
return merge(rangeQuery(l, r, x << 1, lx, m), rangeQuery(l, r, x << 1 | 1, m, rx));
}
Info rangeQuery(int l, int r) {
return rangeQuery(l, r, 1, 0, sz);
}
void rangeApply(int l, int r, const Tag v, int x, int lx, int rx) {
if (l >= rx || lx >= r) {
return;
}
if (l <= lx && rx <= r) {
apply(x, v);
return;
}
int m = (lx + rx) >> 1;
push(x);
rangeApply(l, r, v, x << 1, lx, m);
rangeApply(l, r, v, x << 1 | 1, m, rx);
pull(x);
}
void rangeApply(int l, int r, Tag v) {
rangeApply(l, r, v, 1, 0, sz);
}
};
signed main(int32_t argc, char *argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> sx, sy;
vector<array<int, 2>> c(n);
unordered_map<int, vector<int>> op, cl;
for (int i = 0; i < n; ++i) {
array<int, 2> l, r;
for (auto& x : l) cin >> x;
for (auto& x : r) cin >> x;
sx.push_back(l[0]);
sy.push_back(l[1]);
sx.push_back(r[0]);
sy.push_back(r[1]);
c[i] = {l[1], r[1]};
op[l[0]].push_back(i);
cl[r[0]].push_back(i);
}
unordered_map<int, vector<pair<int, int>>> qry;
while (q--) {
int x, y, clr;
cin >> x >> y >> clr;
sx.push_back(x);
sy.push_back(y);
qry[x].push_back({y, clr});
}
sort(sx.begin(), sx.end());
sx.resize(unique(sx.begin(), sx.end()) - sx.begin());
sort(sy.begin(), sy.end());
sy.resize(unique(sy.begin(), sy.end()) - sy.begin());
for (auto& [l, r] : c) {
l = lower_bound(sy.begin(), sy.end(), l) - sy.begin();
r = lower_bound(sy.begin(), sy.end(), r) - sy.begin();
}
vector<vector<int>> g(n);
vector<int> par(n, -1);
vector<vector<int>> a(n);
LazySegTree<Info, Tag> st(sy.size());
for (int x : sx) {
for (int i : op[x]) {
par[i] = st.query(c[i][0]).v;
if (par[i] != -1) {
g[par[i]].push_back(i);
}
st.rangeApply(c[i][0], c[i][1] + 1, Tag(i));
}
for (auto [y, clr] : qry[x]) {
int id = st.query(lower_bound(sy.begin(), sy.end(), y) - sy.begin()).v;
if (id != -1) {
a[id].push_back(clr);
}
}
for (int i : cl[x]) {
st.rangeApply(c[i][0], c[i][1] + 1, Tag(par[i]));
}
}
vector<set<int>> kek(n);
vector<int> ans(n, 0);
auto Dfs = [&](auto&& self, int u) -> void {
for (auto to : g[u]) {
self(self, to);
if (kek[u].size() < kek[to].size()) swap(kek[u], kek[to]);
while (!kek[to].empty()) {
kek[u].insert(*kek[to].begin()), kek[to].erase(kek[to].begin());
}
}
for (auto x : a[u]) kek[u].insert(x);
ans[u] = (int) kek[u].size();
};
for (int i = 0; i < n; ++i) {
if (par[i] == -1) {
Dfs(Dfs, i);
}
}
for (auto x : ans) cout << x << '\n';
return 0;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
23408 KB |
Output is correct |
| 2 |
Correct |
110 ms |
22744 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
31296 KB |
Output is correct |
| 2 |
Correct |
124 ms |
27440 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
265 ms |
51336 KB |
Output is correct |
| 2 |
Correct |
232 ms |
42044 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
540 ms |
79044 KB |
Output is correct |
| 2 |
Correct |
541 ms |
71740 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
517 ms |
77996 KB |
Output is correct |
| 2 |
Correct |
474 ms |
67156 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
