Submission #701455

#TimeUsernameProblemLanguageResultExecution timeMemory
701455mgl_diamondPlahte (COCI17_plahte)C++14
96 / 160
216 ms50608 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define FOR(i, l, r) for(int i=(l); i<=(r); ++i) #define FORD(i, l, r) for(int i=(l); i>=(r); --i) #define FORE(x, v) for(auto &x : v) #define vec vector #define fi first #define se second #define ins push_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)x.size() #define lc id<<1 #define rc id<<1|1 #define file "input" const int nx = 80008; // tournament tree bool touch[nx * 8]; int sgt[nx * 8]; void app(int id) { if (!touch[id]) return; sgt[lc] = sgt[rc] = sgt[id]; touch[lc] = touch[rc] = 1; touch[id] = 0; } void upd(int id, int lb, int rb, int l, int r, int i) { if (l <= lb && rb <= r) { sgt[id] = i; touch[id] = 1; return; } else if (rb < l || lb > r) return; app(id); int mb = (lb + rb) >> 1; upd(lc, lb, mb, l, r, i); upd(rc, mb+1, rb, l, r, i); } int query(int id, int lb, int rb, int i) { if (lb == rb) return sgt[id]; app(id); int mb = (lb + rb) >> 1; if (i <= mb) return query(lc, lb, mb, i); return query(rc, mb+1, rb, i); } struct rect { int u, v, p, q; rect(int _u=0, int _v=0, int _p=0, int _q=0) : u(_u), v(_v), p(_p), q(_q) {} }; struct ball { int u, v, c; ball(int _u=0, int _v=0, int _c=0) : u(_u), v(_v), c(_c) {} }; int n, m; rect a[nx]; ball balls[nx]; vec<pii> point[nx * 2]; vec<int> stEdge[nx * 2], enEdge[nx * 2]; vec<int> dx, dy; int ans[nx], pa[nx]; vec<int> graph[nx]; set<int> bag[nx]; int pos(int x, vec<int> &v) { return upper_bound(all(v), x) - v.begin(); } void dfs(int u) { FORE(v, graph[u]) { dfs(v); if (bag[u].size() < bag[v].size()) swap(bag[u], bag[v]); for(int x : bag[v]) bag[u].insert(x); } ans[u] = bag[u].size(); } void solve() { cin >> n >> m; FOR(i, 1, n) { int u, v, p, q; cin >> u >> v >> p >> q; a[i] = rect(u, v, p, q); dx.ins(a[i].u); dx.ins(a[i].p); dy.ins(a[i].v); dy.ins(a[i].q); } FOR(i, 1, m) { int u, v, c; cin >> u >> v >> c; balls[i] = ball(u, v, c); dx.ins(u); dy.ins(v); } sort(all(dx)); dx.resize(unique(all(dx)) - dx.begin()); sort(all(dy)); dy.resize(unique(all(dy)) - dy.begin()); // FOR(i, 1, n) { a[i].u = pos(a[i].u, dx); a[i].v = pos(a[i].v, dy); a[i].p = pos(a[i].p, dx); a[i].q = pos(a[i].q, dy); int u = a[i].u, p = a[i].p; stEdge[u].ins(i); enEdge[p].ins(i); } FOR(i, 1, m) { int u = balls[i].u, v = balls[i].v, c = balls[i].c; u = pos(u, dx); v = pos(v, dy); point[u].ins({v, c}); } int init = m; m = sz(dy); FOR(i, 1, sz(dx)) { FORE(x, stEdge[i]) { int l = a[x].v, r = a[x].q; pa[x] = query(1, 1, m, l); graph[pa[x]].ins(x); upd(1, 1, m, l, r, x); } FORE(x, point[i]) { int tmp = query(1, 1, m, x.fi); bag[tmp].insert(x.se); } FORE(x, enEdge[i]) { int l = a[x].v, r = a[x].q; upd(1, 1, m, l, r, pa[x]); } } dfs(0); FOR(i, 1, n) cout << ans[i] << "\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(file".inp", "r")) { freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); } int t = 1; while (t--) solve(); return 0; }

Compilation message (stderr)

plahte.cpp: In function 'void solve()':
plahte.cpp:121:7: warning: unused variable 'init' [-Wunused-variable]
  121 |   int init = m;
      |       ^~~~
plahte.cpp: In function 'int main()':
plahte.cpp:151:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:152:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...