Submission #35609

#TimeUsernameProblemLanguageResultExecution timeMemory
35609szawinisPlahte (COCI17_plahte)C++14
160 / 160
789 ms63632 KiB
#include <bits/stdc++.h> using namespace std; const int N = 8e4+10; struct segtree { int n; vector<priority_queue<pair<int,int>>> t; segtree(int n): n(n) { t.resize(2*n); for(int i = 1; i < 2*n; i++) t[i].emplace(-1, N-1); } void push(int l, int r, int id, int tt) { ++r; for(l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) t[l++].emplace(tt, id); if(r & 1) t[--r].emplace(tt, id); } } void pop(int l, int r) { ++r; for(l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) t[l++].pop(); if(r & 1) t[--r].pop(); } } int query(int i) { pair<int,int> res = {-1, N-1}; for(i += n; i >= 1; i >>= 1) res = max(t[i].top(), res); return res.second; } }; struct query { int x, b, c, tp, id; bool operator<(const query& rhs) const { return (x < rhs.x || (x == rhs.x && tp < rhs.tp)); } }; int n, m, res[N]; vector<query> queries; unordered_set<int> ls[N]; vector<int> ys, g[N]; void compress() { for(query q: queries) { ys.push_back(q.b); if(q.tp) ys.push_back(q.c); } sort(ys.begin(), ys.end()); ys.resize(distance(ys.begin(), unique(ys.begin(), ys.end()))); map<int,int> mp; for(int i = 0; i < ys.size(); i++) mp[ys[i]] = i; for(query& q: queries) { q.b = mp[q.b]; if(q.tp) q.c = mp[q.c]; } } void dfs(int u) { for(int v: g[u]) { dfs(v); if(ls[v].size() > ls[u].size()) swap(ls[u], ls[v]); for(int c: ls[v]) ls[u].insert(c); ls[v].clear(); } res[u] = ls[u].size(); } int main() { scanf("%d %d", &n, &m); for(int i = 0, a, b, c, d; i < n; i++) { scanf("%d %d %d %d", &a, &b, &c, &d); queries.push_back({a, b, d, -1, i}); queries.push_back({c, b, d, 1, i}); } for(int i = 0, a, b, c; i < m; i++) { scanf("%d %d %d", &a, &b, &c); queries.push_back({a, b, c, 0, i}); } sort(queries.begin(), queries.end()); compress(); segtree st = segtree(ys.size()); for(int t = 0; t < queries.size(); t++) { query q = queries[t]; if(q.tp == -1) { g[st.query(q.b)].push_back(q.id); st.push(q.b, q.c, q.id, t); } else if(q.tp == 1) { st.pop(q.b, q.c); } else { int id = st.query(q.b); ls[id].insert(q.c); } } dfs(N-1); for(int i = 0; i < n; i++) printf("%d\n", res[i]); } // root node is N-1

Compilation message (stderr)

plahte.cpp: In function 'void compress()':
plahte.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ys.size(); i++) mp[ys[i]] = i;
                   ^
plahte.cpp: In function 'int main()':
plahte.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int t = 0; t < queries.size(); t++) {
                   ^
plahte.cpp:71:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
plahte.cpp:73:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &a, &b, &c, &d);
                                       ^
plahte.cpp:78:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &c);
                                ^
#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...