Submission #1279550

#TimeUsernameProblemLanguageResultExecution timeMemory
1279550MinhKienPlahte (COCI17_plahte)C++17
160 / 160
264 ms58736 KiB
#include <algorithm> #include <iostream> #include <vector> #include <set> using namespace std; const int N = 8e4 + 10; set <int> ms[N << 1]; bool IsRoot[N << 1]; int n, m, par[N], ans[N]; vector <int> g[N << 1]; vector <int> X, Y; void compress(vector <int> &v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); } struct event { int val, l, r; event () {} event (int VAL, int L, int R) { val = VAL; l = L; r = R; } }; vector <event> ev[N * 3]; vector <int> point[N * 3]; struct rec { int x1, y1, x2, y2, id; void inp() { cin >> x1 >> y1 >> x2 >> y2; X.push_back(x1); X.push_back(x2); Y.push_back(y1); Y.push_back(y2); } bool operator < (const rec &o) const { if (x1 == o.x1) return y1 < o.y1; return x1 < o.x1; } } a[N]; struct shoot { int x, y, k; void inp() { cin >> x >> y >> k; X.push_back(x); Y.push_back(y); } } p[N]; struct SEG { int val[N * 12], lazy[N * 12]; SEG () { fill_n(val, N * 12, 0); fill_n(lazy, N * 12, -1); } void change(int id, int VAL) { val[id] = lazy[id] = VAL; } void down(int id) { if (lazy[id] == -1) return; change(id << 1, lazy[id]); change(id << 1 | 1, lazy[id]); lazy[id] = -1; } void update(int l, int r, int L, int R, int VAL, int id) { if (l > R || r < L) return; if (l >= L && r <= R) { change(id, VAL); return; } int mid = (l + r) >> 1; down(id); update(l, mid, L, R, VAL, id << 1); update(mid + 1, r, L, R, VAL, id << 1 | 1); val[id] = max(val[id << 1], val[id << 1 | 1]); } int get(int l, int r, int u, int id) { if (l == r) return val[id]; int mid = (l + r) >> 1; down(id); if (u <= mid) return get(l, mid, u, id << 1); return get(mid + 1, r, u, id << 1 | 1); } } seg; int ID(int p, vector <int> &v) { return lower_bound(v.begin(), v.end(), p) - v.begin() + 1; } void DFS(int s) { if (s > n) { ms[s].insert(p[s - n].k); } for (int z: g[s]) { DFS(z); if (ms[z].size() > ms[s].size()) swap(ms[z], ms[s]); for (int kk: ms[z]) { ms[s].insert(kk); } } if (s <= n) { ans[a[s].id] = ms[s].size(); } } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; ++i) { a[i].inp(); a[i].id = i; } for (int i = 1; i <= m; ++i) p[i].inp(); sort(a + 1, a + n + 1); compress(X); compress(Y); for (int i = 1; i <= n; ++i) { a[i].x1 = ID(a[i].x1, X); a[i].x2 = ID(a[i].x2, X); a[i].y1 = ID(a[i].y1, Y); a[i].y2 = ID(a[i].y2, Y); ev[a[i].x1].push_back(event(i, a[i].y1, a[i].y2)); ev[a[i].x2].push_back(event(-i, a[i].y1, a[i].y2)); IsRoot[i] = true; } for (int i = 1; i <= m; ++i) { p[i].x = ID(p[i].x, X); p[i].y = ID(p[i].y, Y); point[p[i].x].push_back(i); IsRoot[i + n] = true; } for (int i = 1; i <= (int)X.size(); ++i) { for (event z: ev[i]) { if (z.val > 0) { int kk = seg.get(1, Y.size(), z.l, 1); if (kk) { par[z.val] = kk; g[kk].push_back(z.val); IsRoot[z.val] = false; } seg.update(1, Y.size(), z.l, z.r, z.val, 1); } } for (int z: point[i]) { int kk = seg.get(1, Y.size(), p[z].y, 1); if (kk) { g[kk].push_back(z + n); IsRoot[z + n] = false; } } for (event z: ev[i]) { if (z.val < 0) { seg.update(1, Y.size(), z.l, z.r, par[-z.val], 1); } } } for (int i = 1; i <= n + m; ++i) { if (IsRoot[i]) DFS(i); } for (int i = 1; i <= n; ++i) cout << ans[i] << "\n"; 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...