제출 #1241875

#제출 시각아이디문제언어결과실행 시간메모리
1241875felipe_massaPlahte (COCI17_plahte)C++20
160 / 160
223 ms47436 KiB
#include<bits/stdc++.h> #define int long long using namespace std; #define size(u) (int)(u).size() #define pb push_back #define fastio ios::sync_with_stdio(false); cin.tie(nullptr); #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() struct SegmentTree { int n; vector<int> t, lazy; SegmentTree(int n): n(n), t(4*n, -1), lazy(4*n, -2) {} void apply(int v, int val) { t[v] = val; lazy[v] = val; } void push(int v) { if (lazy[v] == -2) return; apply(2*v, lazy[v]); apply(2*v+1, lazy[v]); lazy[v] = -2; } void update(int v, int tl, int tr, int l, int r, int val) { if (l > tr || tl > r) { return; } else if (tl >= l && tr <= r) { apply(v, val); } else { push(v); int mid = (tl + tr) / 2; update(2*v, tl, mid, l, r, val); update(2*v+1, mid+1, tr, l, r, val); } } void update(int l, int r, int val) { update(1, 0, n-1, l, r, val); } int query(int v, int tl, int tr, int pos) { if (tl == tr) { return t[v]; } else { push(v); int mid = (tl + tr) / 2; if (pos <= mid) return query(2*v, tl, mid, pos); else return query(2*v+1, mid+1, tr, pos); } } int query(int pos) { return query(1, 0, n-1, pos); } }; constexpr int N = 80004; struct point { int x, y, id, prior; bool query = false; bool operator<(point o) { if (x < o.x) return true; if (x > o.x) return false; return prior < o.prior; } }; ostream& operator<<(ostream& out, point p) { return out << p.x << ' ' << p.y << ' ' << p.id << ' ' << p.query; } struct sq { int l, r; } squares[N]; int q[N], parent[N], ans[N]; set<int> smtol[N]; vector<int> ch[N]; vector<int> yvals; bool open[N]; int getyval(int a) { return lower_bound(all(yvals), a) - yvals.begin(); } void dfs(int cur) { for (auto u : ch[cur]) { dfs(u); if (size(smtol[u]) > size(smtol[cur])) smtol[u].swap(smtol[cur]); for (auto t : smtol[u]) smtol[cur].insert(t); } ans[cur] = size(smtol[cur]); } signed main() { fastio; int n, m; cin >> n >> m; vector<point> points; for (int i = 0; i < n; i++) { point p1, p2; cin >> p1.x >> p1.y >> p2.x >> p2.y; p1.id = p2.id = i; p1.prior = -2, p2.prior = 0; points.pb(p1); points.pb(p2); yvals.pb(p1.y); yvals.pb(p2.y); squares[i] = {p1.y, p2.y}; } for (int i = 0; i < m; i++) { point p; cin >> p.x >> p.y; p.id = i, p.query = true; p.prior = -1; points.pb(p); yvals.pb(p.y); cin >> q[i]; } sort(all(yvals)); yvals.erase(unique(all(yvals)), yvals.end()); for (auto & p : points) { p.y = getyval(p.y); } for (int i = 0; i < n; i++) { squares[i].l = getyval(squares[i].l); squares[i].r = getyval(squares[i].r); } sort(all(points)); SegmentTree t(size(yvals)); for (auto p : points) { if (p.query) { int par = t.query(p.y); if (par != -1) smtol[par].insert(q[p.id]); } else { if (open[p.id]) { t.update(squares[p.id].l, squares[p.id].r, parent[p.id]); } else { parent[p.id] = t.query(p.y); if (parent[p.id] != -1) ch[parent[p.id]].pb(p.id); t.update(squares[p.id].l, squares[p.id].r, p.id); open[p.id] = true; } } } for (int i = 0; i < n; i++) { if (parent[i] == -1) dfs(i); } for (int i = 0; i < n; i++) cout << ans[i] << '\n'; }
#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...