Submission #164594

#TimeUsernameProblemLanguageResultExecution timeMemory
164594Rouge_HugoCircle selection (APIO18_circle_selection)C++14
12 / 100
2160 ms111512 KiB
#include <bits/stdc++.h> #define ll long long #define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; int n,x,y,z; const int N=8*100005; int vis[N]; map<int,int>m; pair<int,int>a[N]; set<pair<int,int>>s;vector<int>v[N];vector<int>v1[N]; void cl(int ii ,int r) { for(int i=m[a[ii].first-a[ii].second];i<=m[a[ii].first+a[ii].second];i++) { for(auto it:v[i]) { if (vis[it])continue; s.erase({a[it].second,-it}); vis[it]=r; } for(auto it:v1[i]) { if (vis[it])continue; s.erase({a[it].second,-it}); vis[it]=r; } } } int main() { fast cin>>n; for(int i=0;i<n;i++) { cin>>x>>z;cin>>z; a[i]={x,z}; m[x+z]++;m[x-z]++; } int re=0; for(auto it:m) { m[it.first]=++re; } for(int i=0;i<n;i++) { x=m[a[i].first-a[i].second]; y=m[a[i].first+a[i].second]; v[x].push_back(i);v1[y].push_back(i); } for(int i=0;i<n;i++) s.insert({a[i].second,-i}); while (!s.empty()) { pair<int,int>w=*s.rbegin(); w.second=-w.second; cl(w.second,w.second+1); } for(int i=0;i<n;i++)cout<<vis[i]<<" "; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...