fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  4. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  5. #define ll long long
  6.  
  7. using namespace std;
  8.  
  9. const int N = 1e5 + 5;
  10. int n, pile[N], pre[N];
  11.  
  12. struct Item {
  13.     int a, b, idx;
  14.     bool operator < (const Item &ot) const {
  15.         if (a != ot.a) return a < ot.a;
  16.         return b > ot.b;
  17.     }
  18. } Box[N];
  19.  
  20. void nhap() {
  21.     cin >> n;
  22.     FOR(i, 1, n) cin >> Box[i].a >> Box[i].b, Box[i].idx = i;
  23. }
  24.  
  25. void giai() {
  26.     sort(Box + 1, Box + 1 + n);
  27.     multiset <pair <int, int>> S;
  28.     vector <int> top;
  29.     FOR(i, 1, n) {
  30.         auto [a, b, idx] = Box[i];
  31.         auto it = S.lower_bound({b, -1});
  32.  
  33.         if (it == S.begin()) {
  34.             top.push_back(idx);
  35.             pile[idx] = top.size();
  36.             pre[idx] = -1;
  37.             S.insert({b, pile[idx]});
  38.         }
  39.  
  40.         else {
  41.             --it;
  42.             int pid = it -> second;
  43.             S.erase(it);
  44.             S.insert({b, pid});
  45.             pre[idx] = top[pid - 1];
  46.             pile[i] = pid;
  47.             top[pid - 1] = idx;
  48.         }
  49.     }
  50.  
  51.     cout << top.size() << '\n';
  52.     for (int x : top) {
  53.         vector <int> res;
  54.         int cur = x;
  55.         while (cur != -1) {
  56.             res.push_back(cur);
  57.             cur = pre[cur];
  58.         }
  59.         cout << res.size() << ' ';
  60.         for (int i : res) cout << i << ' ';
  61.         cout << '\n';
  62.     }
  63. }
  64.  
  65. int main() {
  66.     ios_base::sync_with_stdio(0);
  67.     cin.tie(0); cout.tie(0);
  68.  
  69.     #define name "test"
  70.  
  71.     if (fopen(name".inp", "r")) {
  72.         freopen(name".inp", "r", stdin);
  73.         freopen(name".out", "w", stdout);
  74.     }
  75.  
  76.     nhap();
  77.     giai();
  78.  
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/UCfw6n
language:
C++14 (clang 8.0)
created:
16 hours ago
visibility:
public

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!