fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct pt{
  4. 	int x,y,z,id;
  5. };
  6. int main() {
  7. 	ios::sync_with_stdio(false);
  8. 	cin.tie(0);
  9.     vector<pt> vec;
  10.     int n;
  11.     cin>>n;
  12.     for(int i=0;i<n;++i){
  13.         pt p;
  14.         p.id=i+1;
  15.         cin>>p.x>>p.y>>p.z;
  16.         vec.push_back(p);
  17.     }
  18.     auto cmpSet = [](pt a, pt b) { return a.x<b.x;};
  19.     std::set<pt, decltype(cmpSet)> s(cmpSet);
  20.     sort(vec.begin(),vec.end(),[](pt a, pt b) { return a.z<b.z;}) ;
  21.  
  22.     vector<int> ans;
  23.     for(auto p:vec){
  24.         auto [lower,upper]= s.equal_range(p);
  25.         if(lower!=s.end()&&(*lower).y>=p.y) continue;
  26.         if(upper==s.begin()){
  27.             s.insert(p);
  28.             continue;
  29.         }
  30.         auto it = std::make_reverse_iterator(upper);
  31.         while (it != s.rend() && (*it).y <= p.y) {
  32.         	if((*it).z<p.z) ans.push_back((*it).id);
  33.         	auto victim = std::prev(it.base());
  34.         	it = std::next(it);
  35.         	s.erase(victim);
  36.         }
  37.         s.insert(p);
  38.     }
  39.     for(auto p: s) ans.push_back(p.id);
  40.     sort(ans.begin(),ans.end());
  41.     for(int i=0;i<ans.size();++i) cout<<ans[i]<<(i==ans.size()-1?'\n':' ');
  42.     return 0;
  43. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5
10 1000 50
12 900 55
10 1200 45
11 1100 48
8  1500 40
stdout
copy 
2 3 4 5
https://ideone.com/KOLoF9
language:
C++14 (gcc 8.3)
created:
95 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!