Submission #1237737

#TimeUsernameProblemLanguageResultExecution timeMemory
1237737EliudGarciaPlahte (COCI17_plahte)C++17
0 / 160
235 ms39600 KiB
#include <bits/stdc++.h> using namespace std; #define ln '\n' #define all(x) x.begin(), x.end() #define forn(i, n) for(int i = 0; i < n; i++) #define forab(i, a, b) for (int i = a; i < b; i++) #define pb push_back #define sz(x) int(x.size()) #define rforn(i, n) for (int i = n-1; i >= 0; --i) #define form(i, n, m, x) for (int i = n; i < m; i += x) #define rform(i, n, m, x) for (int i = n; i >= m; i -= x) #ifdef LOCAL #include "debug.cpp" #else #define dbg(...) #endif typedef long long ll; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<ll> vll; template<typename T> void print(T *a, int l, int r){ cout << "===> ["; for(int i = l; i < r; i++){ if(i == r - 1) cout << (a[i]) << "]\n"; else cout << a[i] << ", "; } } template<typename T> struct STree { int n; vector<T> st, lazy; T neutro = T(0); STree(int m) { n = m; st.resize(n * 4); lazy.resize(n * 4); } STree(vector<T> &a) { n = sz(a); st.resize(n * 4); lazy.resize(n * 4); build(1, 0, n - 1, a); } T oper(T a, T b) { return max(a, b); } void build(int v, int tl, int tr, vector<T> &a) { if(tl == tr) { st[v] = a[tl]; return; } int tm = (tl + tr) / 2; build(v * 2, tl, tm, a); build(v * 2 + 1, tm + 1, tr, a); st[v] = oper(st[v * 2], st[v * 2 + 1]); } void push(int v, int tl, int tr) { if (!lazy[v]) return; st[v] = lazy[v]; if (tl != tr) { lazy[v * 2] = lazy[v]; lazy[v * 2 + 1] = lazy[v]; } lazy[v] = 0; } void upd(int v, int tl, int tr, int l, int r, T val) { push(v, tl, tr); if(tr < l || tl > r) return; if (tl >= l && tr <= r) { lazy[v] = val; push(v, tl, tr); return; } int tm = (tl + tr) / 2; upd(v * 2, tl, tm, l, r, val); upd(v * 2 + 1, tm + 1, tr, l, r, val); st[v] = oper(st[v * 2], st[v * 2 + 1]); } T query(int v, int tl, int tr, int l, int r) { push(v, tl, tr); if(tl > r || tr < l) return neutro; if (l <= tl && tr <= r) return st[v]; int tm = (tl + tr) / 2; return oper(query(v * 2, tl, tm, l, r), query(v * 2 + 1, tm + 1, tr, l, r)); } void upd(int l, int r, T val) { upd(1, 0, n - 1, l, r, val); } T query(int l, int r) { return query(1, 0, n - 1, l, r); } }; struct event { int x, y, id, t; bool operator < (event &o) const { if(x == o.x) return t < o.t; return x < o.x; } }; int n, m; const int MAXN = 80005; vector<array<int, 4>> rec(MAXN); vector<array<int, 3>> pts(MAXN); int parent[MAXN]; vi g[MAXN]; bool vis[MAXN]; int ans[MAXN]; set<int> dsu[MAXN]; vector<event> order; vi compression; int get_id(int x){ return lower_bound(all(compression), x) - compression.begin(); } set<int> dfs(int u, int p){ if(vis[u]) return {}; vis[u] = 1; set<int> a = dsu[u]; for(int v: g[u]){ if(!vis[v]){ set<int> b = dfs(v, u); if(sz(a) < sz(b)) swap(a, b); for(int i: b){ a.insert(i); } } } //dbg(u, a); ans[u] = sz(a); return a; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif cin >> n >> m; forab(i, 1, n + 1){ int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; rec[i] = {x1, y1, x2, y2}; order.pb({x1, y1, i, 0}); order.pb({x2, y2, i, 2}); //int height = abs(y2 - y1); compression.pb(y1); compression.pb(y2); } forab(i, 1, m + 1){ int x, y, c; cin >> x >> y >> c; pts[i] = {x, y, c}; order.pb({x, y, i, 1}); compression.pb(y); } sort(all(order)); sort(all(compression)); compression.erase(unique(all(compression)), compression.end()); vi aux(sz(compression) + 1, n + 1); forab(i, 1, n + 1) parent[i] = n + 1; STree<int> st(aux); for(auto [x, y, i, type] : order){ if(type == 0){ //printf("REC INICIO\n"); auto [x1, y1, x2, y2] = rec[i]; int l = get_id(y1); int r = get_id(y2); parent[i] = st.query(l, r); st.upd(l, r, i); }else if(type == 1){ //printf("PUNTO\n"); int idx = get_id(y); int p = st.query(idx, idx); dsu[p].insert(pts[i][2]); //printf("Contenido en: %d\n", p); }else{ //printf("REC FIN\n"); auto [x1, y1, x2, y2] = rec[i]; int l = get_id(y1); int r = get_id(y2); st.upd(l, r, parent[i]); } //printf("%d %d\n", x, y); //printf("==================\n"); } forab(i, 1, n + 1){ if(parent[i] == n + 1) continue; g[parent[i]].pb(i); g[i].pb(parent[i]); } /* forab(i, 1, n + 1){ dbg(i, parent[i]); } */ forab(i, 1, n + 1){ if(!vis[i]) dfs(i, parent[i]); } forab(i, 1, n + 1) { cout << ans[i] << ln; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...