fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define pub push_back
  7. #define pob pop_back
  8. #define mpa make_pair
  9. #define endl '\n'
  10. #define BIT(i) ((1 << i))
  11. const int maxn = 1e5 + 10;
  12. int n;
  13. vector<int> nen;
  14. pair<pair<int, int>, int> a[maxn];
  15. bool cmp(pair<pair<int, int>, int> x, pair<pair<int, int>, int> y)
  16. {
  17.     if(x.fi.fi == y.fi.fi) return x.fi.se > y.fi.se;
  18.     return x.fi.fi < y.fi.fi;
  19. }
  20.  
  21. pair<int, int> seg[maxn * 4];
  22. void update(int id, int l, int r, int x, int val, int cs)
  23. {
  24.     if(l > x || r < x) return ;
  25.     if(l == r)
  26.     {
  27.         seg[id] = {val, cs};
  28.         return ;
  29.     }
  30.     int mid = l + r >> 1;
  31.     update(id << 1, l, mid, x, val, cs);
  32.     update(id << 1 | 1, mid + 1, r, x, val, cs);
  33.     seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
  34. }
  35.  
  36. pair<int, int> get(int id, int l, int r, int x, int y)
  37. {
  38.     if(l > y || r < x) return {0, 0};
  39.     if(l >= x && r <= y) return seg[id];
  40.     int mid = l + r >> 1;
  41.     return max(get(id << 1, l, mid, x, y), get(id << 1 | 1, mid + 1, r, x, y));
  42. }
  43. int trace[maxn];
  44. int vt[maxn];
  45. int mp[maxn];
  46. bool check[maxn];
  47. vector<int> ans[maxn];
  48. int bangnhau[maxn];
  49. int main()
  50. {
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(0);
  53.     cout.tie(0);
  54.     #define code code
  55. //    freopen("code.INP","r",stdin);
  56. //    freopen("code.OUT","w",stdout);
  57.     cin >> n;
  58.     nen.pub(-1e9);
  59.     for(int i=1; i<=n; i++)
  60.     {
  61.         int x, y;
  62.         cin >> x >> y;
  63.         a[i] = {{x, y}, i};
  64.         nen.pub(y);
  65.     }
  66.     sort(a + 1, a + n + 1, cmp);
  67.     sort(nen.begin(), nen.end());
  68. //    cout << endl;
  69.     for(int i=1; i<=n; i++)
  70.     {
  71. //        cout << a[i].fi.fi << " " << a[i].fi.se << endl;
  72.     }
  73. //    cout << endl;
  74.     for(int i=1; i<=n; i++)
  75.     {
  76.         int p = upper_bound(nen.begin(), nen.end(), a[i].fi.se - 1) - nen.begin();
  77.         int pos = p + mp[p];
  78.         pair<int, int> res = get(1, 1, n, 1, p - 1);
  79.         vt[i] = pos;
  80.         trace[i] = res.se;
  81.         update(1, 1, n, pos, pos, i);
  82.         update(1, 1, n, vt[res.se], 0, 0);
  83.         mp[p]++;
  84.     }
  85.     int cnt = 0;
  86.     for(int i=n; i>=1; i--)
  87.     {
  88.         int p = i;
  89.         bool ok = false;
  90.         while(check[p] == false && p > 0)
  91.         {
  92.             check[p] = true;
  93.             ans[cnt].pub(p);
  94.             p = trace[p];
  95.             ok = true;
  96.         }
  97.         cnt += ok;
  98.     }
  99.     cout << cnt << endl;
  100.     for(int i=0; i<cnt; i++)
  101.     {
  102.         cout << ans[i].size() << " ";
  103.         for(int x : ans[i]) cout << a[x].se << " ";
  104.         cout << endl;
  105.     }
  106.     return 0;
  107. }
Success #stdin #stdout 0.01s 7500KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/4obvBA
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!