# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
866016 |
2023-10-25T09:51:57 Z |
hafo |
Plahte (COCI17_plahte) |
C++14 |
|
318 ms |
101820 KB |
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 3e5 + 7;
const ll oo = 1e18 + 69;
int n, m, p[2][maxn], res[maxn];
vector<int> g[maxn], c[maxn];
set<int> s[maxn];
struct rec {
int x, y, u, v;
} a[maxn];
struct query {
int x, y, k;
} que[maxn];
vector<int> vx, vy, ev[4][maxn];
int idx(int x) {
return lower_bound(all(vx), x) - vx.begin();
}
int idy(int y) {
return lower_bound(all(vy), y) - vy.begin() + 1;
}
struct ST {
int st[4 * maxn], lz[4 * maxn];
void init(int n) {
for(int i = 1; i <= 4 * n; i++) {
st[i] = 0;
lz[i] = -1;
}
}
void fix(int id, int l, int r) {
if(lz[id] == -1) return;
if(l == r) st[id] = lz[id];
else {
lz[id << 1] = lz[id];
lz[id << 1 | 1] = lz[id];
}
lz[id] = -1;
}
void update(int id, int l, int r, int u, int v, int val) {
fix(id, l, r);
if(r < u || l > v) return;
if(u <= l && r <= v) {
lz[id] = val;
fix(id, l, r);
return;
}
int mid = l + r >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
}
int get(int id, int l, int r, int pos) {
fix(id, l, r);
if(pos < l || pos > r) return 0;
if(l == r) return st[id];
int mid = l + r >> 1;
return get(id << 1, l, mid, pos) + get(id << 1 | 1, mid + 1, r, pos);
}
} st;
void dfs(int u, int par) {
for(auto v:g[u]) {
if(v == par) continue;
dfs(v, u);
if(Size(s[u]) < Size(s[v])) s[u].swap(s[v]);
for(auto i:s[v]) s[u].insert(i);
}
res[u] = Size(s[u]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen(TASK".inp", "r", stdin);
//freopen(TASK".out", "w", stdout);
cin>>n>>m;
for(int i = 1; i <= n; i++) {
cin>>a[i].x>>a[i].y>>a[i].u>>a[i].v;
vx.pb(a[i].x);
vx.pb(a[i].u);
vy.pb(a[i].y);
vy.pb(a[i].v);
}
for(int i = 1; i <= m; i++) {
cin>>que[i].x>>que[i].y>>que[i].k;
vx.pb(que[i].x);
vy.pb(que[i].y);
}
sort(all(vx));
sort(all(vy));
vx.erase(unique(all(vx)), vx.end());
vy.erase(unique(all(vy)), vy.end());
for(int i = 1; i <= n; i++) {
int id = idx(a[i].x);
ev[0][id].pb(i);
id = idx(a[i].u);
ev[1][id].pb(i);
}
for(int i = 1; i <= m; i++) {
int id = idx(que[i].x);
ev[2][id].pb(i);
}
st.init(Size(vy));
for(int i = 0; i < Size(vx); i++) {
for(auto j:ev[0][i]) {
int l = idy(a[j].y);
int r = idy(a[j].v);
p[0][j] = st.get(1, 1, Size(vy), l);
st.update(1, 1, Size(vy), l, r, j);
}
for(auto j:ev[2][i]) {
int id = idy(que[j].y);
p[1][j] = st.get(1, 1, Size(vy), id);
}
for(auto j:ev[1][i]) {
int l = idy(a[j].y);
int r = idy(a[j].v);
st.update(1, 1, Size(vy), l, r, p[0][j]);
}
}
for(int i = 1; i <= n; i++) {
g[p[0][i]].pb(i);
}
for(int i = 1; i <= m; i++) {
if(p[1][i] == 0) continue;
s[p[1][i]].insert(que[i].k);
}
dfs(0, 0);
for(int i = 1; i <= n; i++) cout<<res[i]<<"\n";
return 0;
}
Compilation message
plahte.cpp: In member function 'void ST::update(int, int, int, int, int, int)':
plahte.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int mid = l + r >> 1;
| ~~^~~
plahte.cpp: In member function 'int ST::get(int, int, int, int)':
plahte.cpp:81:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
81 | int mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
77744 KB |
Output is correct |
2 |
Correct |
115 ms |
78316 KB |
Output is correct |
3 |
Correct |
13 ms |
66140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
79584 KB |
Output is correct |
2 |
Correct |
119 ms |
78904 KB |
Output is correct |
3 |
Correct |
13 ms |
66136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
191 ms |
91320 KB |
Output is correct |
2 |
Correct |
188 ms |
85696 KB |
Output is correct |
3 |
Correct |
13 ms |
65884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
307 ms |
101820 KB |
Output is correct |
2 |
Correct |
318 ms |
96964 KB |
Output is correct |
3 |
Correct |
13 ms |
65880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
315 ms |
99492 KB |
Output is correct |
2 |
Correct |
309 ms |
95556 KB |
Output is correct |
3 |
Correct |
13 ms |
66140 KB |
Output is correct |