Submission #1190620

#TimeUsernameProblemLanguageResultExecution timeMemory
1190620MalixCircle selection (APIO18_circle_selection)C++20
12 / 100
653 ms52972 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<ll,ll,ll> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; int main() { // ios::sync_with_stdio(0); // cin.tie(0); int n;cin>>n; vector<ti> a(n); vector<pair<ll,int>> b(n); set<pair<ll,int>> L,R; REP(i,0,n){ ll x,y,z;cin>>x>>y>>z; a[i]={x,y,z}; b[i]={z,-i}; L.insert({x-z,i}); R.insert({x+z,i}); } vi ans(n); REP(i,0,n)ans[i]=i; sort(b.begin(),b.end()); reverse(b.begin(),b.end()); REP(i,0,n){ int pos=-b[i].S; if(ans[pos]!=pos)continue; int l=get<0>(a[pos])-get<2>(a[pos]); int r=get<0>(a[pos])+get<2>(a[pos]); L.erase({l,pos}); R.erase({r,pos}); auto it=L.lower_bound({l,-1}); while(it!=L.end()&&it->F>=l&&it->F<=r){ int k=it->S; it++; ans[k]=pos; L.erase({get<0>(a[k])-get<2>(a[k]),k}); R.erase({get<0>(a[k])+get<2>(a[k]),k}); } it=R.upper_bound({r,n}); if(it==R.begin())continue; it--; while(!R.empty()&&it->F>=l&&it->F<=r){ int k=it->S; it--; ans[k]=pos; L.erase({get<0>(a[k])-get<2>(a[k]),k}); R.erase({get<0>(a[k])+get<2>(a[k]),k}); } } REP(i,0,n)cout<<ans[i]+1<<" "; }
#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...