| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1096729 |
2024-10-05T04:21:57 Z |
Perl32 |
Plahte (COCI17_plahte) |
C++14 |
|
233 ms |
34752 KB |
//I wrote this code 4 u <3
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Info {
int v = -1;
Info() = default;
Info(int x) : v(x) {}
};
Info operator+(const Info &a, const Info &b) {
Info ret;
ret.v = a.v + b.v;
return ret;
}
struct Tag {
int v = -1;
bool s = 0;
Tag() = default;
explicit Tag(int x) {
v = x;
s = 1;
}
};
void apply(Info &a, Tag b) {
if (b.s) a.v = b.v;
}
void apply(Tag &a, Tag b) {
if (b.s) 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 < (int) a.size()) 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();
}
Info get(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(get(l, r, x << 1, lx, m), get(l, r, x << 1 | 1, m, rx));
}
Info get(int l, int r) {
return get(l, r, 1, 0, sz);
}
Info get(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 get(i, x << 1, lx, m);
} else {
return get(i, x << 1 | 1, m, rx);
}
}
Info get(int i) {
return get(i, 1, 0, sz);
}
void upd(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);
upd(l, r, v, x << 1, lx, m);
upd(l, r, v, x << 1 | 1, m, rx);
pull(x);
}
void upd(int l, int r, Tag v) {
upd(l, r, v, 1, 0, sz);
}
void upd(int i, Info v, int x, int lx, int rx) {
if (lx + 1 == rx) {
t[x] = v;
return;
}
int m = (lx + rx) >> 1;
push(x);
if (i < m) {
upd(i, v, x << 1, lx, m);
} else {
upd(i, v, x << 1 | 1, m, rx);
}
pull(x);
}
void upd(int i, Info v) {
upd(i, v, 1, 0, sz);
}
};
signed main(int32_t argc, char *argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> srt;
vector<array<int, 5>> ev(2 * n + m);
for (int i = 0; i < n; ++i) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
srt.push_back(y1);
srt.push_back(y2);
ev[i << 1] = {x1, -1, i, y1, y2};
ev[i << 1 | 1] = {x2, 1, i, y1, y2};
}
for (int i = 0; i < m; ++i) {
int x, y, c;
cin >> x >> y >> c;
srt.push_back(y);
ev[2 * n + i] = {x, 0, i, y, c};
}
sort(srt.begin(), srt.end());
srt.resize(unique(srt.begin(), srt.end()) - srt.begin());
vector<set<int>> pizda(n);
vector<vector<int>> g(n);
vector<int> par(n, -1);
LazySegTree<Info, Tag> st(srt.size());
sort(ev.begin(), ev.end());
for (auto [x, t, i, y1, y2] : ev) {
if (t == -1) {
y1 = lower_bound(srt.begin(), srt.end(), y1) - srt.begin();
y2 = lower_bound(srt.begin(), srt.end(), y2) - srt.begin();
par[i] = st.get(y1).v;
if (par[i] > -1) g[par[i]].push_back(i);
st.upd(y1, y2 + 1, Tag(i));
} else if (!t) {
y1 = lower_bound(srt.begin(), srt.end(), y1) - srt.begin();
int kek = st.get(y1).v;
if (kek > -1) pizda[kek].insert(y2);
} else {
y1 = lower_bound(srt.begin(), srt.end(), y1) - srt.begin();
y2 = lower_bound(srt.begin(), srt.end(), y2) - srt.begin();
st.upd(y1, y2 + 1, Tag(par[i]));
}
}
vector<int> ans(n);
auto Dfs = [&](auto&& self, int u) -> void {
for (auto to : g[u]) {
self(self, to);
if (pizda[u].size() < pizda[to].size()) swap(pizda[u], pizda[to]);
while (!pizda[to].empty()) {
int x = *pizda[to].begin(); pizda[to].erase(pizda[to].begin());
pizda[u].insert(x);
}
}
ans[u] = pizda[u].size();
};
for (int i = 0; i < n; ++i) {
if (par[i] == -1) Dfs(Dfs, i);
}
for (auto x : ans) cout << x << '\n';
}
/*
*/
Compilation message
plahte.cpp: In function 'int main(int32_t, char**)':
plahte.cpp:189:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
189 | for (auto [x, t, i, y1, y2] : ev) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
9996 KB |
Output is correct |
| 2 |
Correct |
60 ms |
9640 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
13116 KB |
Output is correct |
| 2 |
Correct |
72 ms |
11732 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
23968 KB |
Output is correct |
| 2 |
Correct |
131 ms |
16584 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
214 ms |
34752 KB |
Output is correct |
| 2 |
Correct |
221 ms |
27572 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
32244 KB |
Output is correct |
| 2 |
Correct |
233 ms |
27108 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
