Submission #404750

#TimeUsernameProblemLanguageResultExecution timeMemory
404750jeroenodbPlahte (COCI17_plahte)C++14
160 / 160
752 ms379048 KiB
#include "bits/stdc++.h" using namespace std; #define all(x) begin(x),end(x) template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; } #define debug(a) cerr << "(" << #a << ": " << a << ")\n"; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pi; #ifndef LOCAL const int mxN = 8e4+1, oo = 1e9; #else const int mxN = 1e2+1, oo = 1e9; #endif unordered_set<int> colours[mxN]; int ans[mxN]; vi kid[mxN]; bitset<mxN> notroot; void dfs(int at) { for(int to:kid[at]) { dfs(to); if(colours[to].size()>colours[at].size()) { swap(colours[at],colours[to]); } for(auto c: colours[to]) colours[at].insert(c); } ans[at] = colours[at].size(); } struct tourtree { vector<stack<int>> seg; int ptwo = 1; tourtree() {} tourtree(int n) { n+=3; while(ptwo<n) ptwo*=2; seg.resize(ptwo*2); } void put(int l, int r, int i) { for(l+=ptwo,r+=ptwo;l>0 and l<r;l/=2,r/=2) { if(l&1) seg[l++].push(i); if(r&1) seg[--r].push(i); } } void take(int l, int r) { for(l+=ptwo,r+=ptwo;l>0 and l<r;l/=2,r/=2) { if(l&1) seg[l++].pop(); if(r&1) seg[--r].pop(); } } int get(int y) { int res = -1; for(y+=ptwo;y>0;y/=2) { if(!seg[y].empty()) res = max(res,seg[y].top()); } return res; } } seg; vi coord; // coord compression on y axis int real(int i) { return lower_bound(all(coord),i)-coord.begin(); } struct event { int x,y1,y2=-oo,i=-1; bool end = false, sheet=true; event() {} event(int X,int Y1, int Y2, int I, bool End) : x(X),y1(Y1),y2(Y2),i(I) { if(End) { coord.push_back(y1); coord.push_back(y2); end=true; } } bool operator<(const event& o) const { if(x==o.x) { if(sheet==o.sheet) return end<o.end; else if(sheet) return !end; else return o.end; } return x<o.x; } }; int main() { int n,m; cin >> n >> m; coord.reserve(2*n+1+m); coord.push_back(oo+100); vector<event> es(2*n+m); for(int i=0;i<n;++i) { auto& e1 = es[2*i],&e2 = es[2*i+1]; int a,b,c,d; cin >> a >> b >> c >> d; e1 = event(a,b,d,i,false); e2 = event(c,b,d,i,true); } for(int i=2*n;i<2*n+m;++i) { auto& b = es[i]; cin >> b.x >> b.y1 >> b.i; b.sheet = false; coord.push_back(b.y1); } sort(all(coord)); coord.erase(unique(all(coord)),coord.end()); seg = tourtree(coord.size()); sort(all(es)); int level = 0; for(auto& e : es) { e.y1 = real(e.y1); auto getsheet = [&](int y) { int j = seg.get(y); if(j==-1) return -1; return es[j].i; }; if(e.sheet) { e.y2 = real(e.y2); if(e.end) { // remove sheet from tour tree seg.take(e.y1,e.y2+1); } else { int par = getsheet(e.y1); if(par!=-1){ kid[par].push_back(e.i); notroot[e.i] = true; } seg.put(e.y1,e.y2+1,level); } } else { // shoot paintball int target = getsheet(e.y1); if(target!=-1) colours[target].insert(e.i); } level++; } for(int i=0;i<n;++i) { if(!notroot[i]) 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...