| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1108804 |
2024-11-05T06:42:13 Z |
juliany2 |
Plahte (COCI17_plahte) |
C++17 |
|
322 ms |
74988 KB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
template<class T> struct LZ_ST {
static constexpr T ID = 2e9, LZ_ID = -1; // or whatever ID
inline T comb(T a, T b) { return min(a, b); } // or whatever function
int sz;
vector<T> t, lz;
void init(int _sz, T val = ID) {
sz = _sz;
t.assign(sz * 4, val);
lz.assign(sz * 4, LZ_ID);
}
inline void push(int l, int r, int v) {
if (lz[v] != LZ_ID && l != r) { // might have to change
int m = l + r >> 1;
//change if set (=) or adding(+=) on range
t[v * 2] = lz[v];
t[v * 2 + 1] = lz[v];
lz[v * 2] = lz[v];
lz[v * 2 + 1] = lz[v];
}
lz[v] = LZ_ID;
}
void upd(int ql, int qr, T x, int l, int r, int v) {
if (qr < l || ql > r) return;
if (l >= ql && r <= qr) // might have to change, same as above
t[v] = x, lz[v] = x;
else {
push(l, r, v);
int m = l + r >> 1;
upd(ql, qr, x, l, m, v * 2);
upd(ql, qr, x, m + 1, r, v * 2 + 1);
t[v] = comb(t[v * 2], t[v * 2 + 1]);
}
}
void upd(int ql, int qr, T x) {
return upd(ql, qr, x, 0, sz - 1, 1);
}
T query(int ql, int qr, int l, int r, int v) {
if (qr < l || ql > r) return ID;
if (l >= ql && r <= qr) return t[v];
push(l, r, v);
int m = l + r >> 1;
return comb(query(ql, qr, l, m, v * 2), query(ql, qr, m + 1, r, v * 2 + 1));
}
T query(int ql, int qr) {
return query(ql, qr, 0, sz - 1, 1);
}
T query(int x) {
return query(x, x);
}
};
const int N = 3e5 + 7;
int n, m;
array<int, 4> a[N];
array<int, 3> b[N];
vector<int> e[N], qry[N], adj[N];
set<int> s[N];
int p[N], ans[N];
LZ_ST<int> st;
void dfs(int v = 0, int p = -1) {
for (int u : adj[v]) {
if (u == p)
continue;
dfs(u, v);
if (s[u].size() > s[v].size())
s[u].swap(s[v]);
for (int x : s[u])
s[v].insert(x);
}
ans[v] = s[v].size();
}
int main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m;
vector<int> x, y;
for (int i = 1; i <= n; i++) {
cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
x.push_back(a[i][0]);
y.push_back(a[i][1]);
x.push_back(a[i][2]);
y.push_back(a[i][3]);
}
for (int i = 1; i <= m; i++) {
cin >> b[i][0] >> b[i][1] >> b[i][2];
x.push_back(b[i][0]);
y.push_back(b[i][1]);
}
sort(all(x));
x.erase(unique(all(x)), x.end());
sort(all(y));
y.erase(unique(all(y)), y.end());
for (int i = 1; i <= n; i++) {
a[i][0] = lower_bound(all(x), a[i][0]) - x.begin();
a[i][1] = lower_bound(all(y), a[i][1]) - y.begin();
a[i][2] = lower_bound(all(x), a[i][2]) - x.begin();
a[i][3] = lower_bound(all(y), a[i][3]) - y.begin();
e[a[i][0]].push_back(i);
e[a[i][2] + 1].push_back(-i);
}
for (int i = 1; i <= m; i++) {
b[i][0] = lower_bound(all(x), b[i][0]) - x.begin();
b[i][1] = lower_bound(all(y), b[i][1]) - y.begin();
qry[b[i][0]].push_back(i);
}
st.init(N, 0);
for (int i = 0; i < N; i++) {
for (int j : e[i]) {
if (j < 0) {
j = -j;
st.upd(a[j][1], a[j][3], p[j]);
}
}
for (int j : e[i]) {
if (j > 0) {
p[j] = st.query(a[j][1]);
st.upd(a[j][1], a[j][3], j);
}
}
for (int j : qry[i]) {
int t = st.query(b[j][1]);
s[t].insert(b[j][2]);
}
}
for (int i = 1; i <= n; i++) {
adj[p[i]].push_back(i);
}
dfs();
for (int i = 1; i <= n; i++)
cout << ans[i] << '\n';
return 0;
}
Compilation message
plahte.cpp: In instantiation of 'void LZ_ST<T>::upd(int, int, T, int, int, int) [with T = int]':
plahte.cpp:42:19: required from 'void LZ_ST<T>::upd(int, int, T) [with T = int]'
plahte.cpp:133:46: required from here
plahte.cpp:35:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int m = l + r >> 1;
| ~~^~~
plahte.cpp: In instantiation of 'void LZ_ST<T>::push(int, int, int) [with T = int]':
plahte.cpp:34:13: required from 'void LZ_ST<T>::upd(int, int, T, int, int, int) [with T = int]'
plahte.cpp:42:19: required from 'void LZ_ST<T>::upd(int, int, T) [with T = int]'
plahte.cpp:133:46: required from here
plahte.cpp:20:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
20 | int m = l + r >> 1;
| ~~^~~
plahte.cpp:20:17: warning: unused variable 'm' [-Wunused-variable]
20 | int m = l + r >> 1;
| ^
plahte.cpp: In instantiation of 'T LZ_ST<T>::query(int, int, int, int, int) [with T = int]':
plahte.cpp:52:21: required from 'T LZ_ST<T>::query(int, int) [with T = int]'
plahte.cpp:55:21: required from 'T LZ_ST<T>::query(int) [with T = int]'
plahte.cpp:139:40: required from here
plahte.cpp:48:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | int m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
58556 KB |
Output is correct |
| 2 |
Correct |
92 ms |
59076 KB |
Output is correct |
| 3 |
Correct |
11 ms |
50768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
60092 KB |
Output is correct |
| 2 |
Correct |
109 ms |
59324 KB |
Output is correct |
| 3 |
Correct |
10 ms |
50768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
185 ms |
66444 KB |
Output is correct |
| 2 |
Correct |
195 ms |
62340 KB |
Output is correct |
| 3 |
Correct |
10 ms |
50768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
313 ms |
74988 KB |
Output is correct |
| 2 |
Correct |
316 ms |
74684 KB |
Output is correct |
| 3 |
Correct |
11 ms |
50768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
322 ms |
72264 KB |
Output is correct |
| 2 |
Correct |
279 ms |
72884 KB |
Output is correct |
| 3 |
Correct |
14 ms |
50768 KB |
Output is correct |
