fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define mp make_pair
  5. #define fst first
  6. #define snd second
  7. #define forn(i, n) for (int i = 0; i < int(n); ++i)
  8. typedef long long ll;
  9. typedef vector<int> vi;
  10. typedef vector<vi> vvi;
  11. typedef vector<ll> vll;
  12. typedef pair<int, int> pii;
  13. typedef vector<pii> vii;
  14. #define sz(c) (int)(c).size()
  15. #define ALL(c) (c).begin(), (c).end()
  16.  
  17. void compr (vi &a)
  18. {
  19.     vi cur = a;
  20.     sort(ALL(cur));
  21.     cur.resize(unique(ALL(cur)) - cur.begin());
  22.     forn (i, sz(a))
  23.         a[i] = lower_bound(ALL(cur), a[i]) - cur.begin();
  24. }
  25.  
  26. const int inf = (int)1e9;
  27.  
  28. struct segtree
  29. {
  30.     int tsz;
  31.     vii vals;
  32.  
  33.     segtree ()
  34.     {
  35.         tsz = -1;
  36.     }
  37.  
  38.     segtree (int n)
  39.     {
  40.         tsz = 1;
  41.         while (tsz < n)
  42.             tsz *= 2;
  43.  
  44.         vals.assign(2 * tsz, mp(0, 0));
  45.     }
  46.  
  47.     void put (int pos, const pii &what)
  48.     {
  49.         vals[pos += tsz] = what;
  50.         for (pos >>= 1; pos > 0; pos >>= 1)
  51.             vals[pos] = max(vals[2 * pos], vals[2 * pos + 1]);
  52.     }
  53.  
  54.     pii getseg (int l, int r)
  55.     {
  56.         pii ans(0, 0);
  57.         for (l += tsz, r += tsz; l < r; l >>= 1, r >>= 1)
  58.         {
  59.             if (l & 1)
  60.                 ans = max(ans, vals[l++]);
  61.             if (r & 1)
  62.                 ans = max(ans, vals[--r]);
  63.         }
  64.         return ans;
  65.     }
  66. };
  67.  
  68. struct segtree2d
  69. {
  70.     vector<segtree> vals;
  71.     vector<vii> who;
  72.     int tsz = 1;
  73.  
  74.     segtree2d (const vi &a, const vi &b)
  75.     {
  76.         const int A = *max_element(ALL(a));
  77.         const int n = sz(a);
  78.  
  79.         tsz = 1;
  80.         while (tsz <= A + 1)
  81.             tsz *= 2;
  82.  
  83.         vals.resize(2 * tsz);
  84.         who.resize(2 * tsz);
  85.         forn (i, n)
  86.             who[a[i] + tsz].pb(mp(b[i], -i));
  87.  
  88.         forn (i, A + 1)
  89.             sort(ALL(who[i + tsz]));
  90.  
  91.         for (int i = tsz - 1; i >= 1; i--)
  92.         {
  93.             who[i].resize(sz(who[2 * i]) + sz(who[2 * i + 1]));
  94.             merge(ALL(who[2 * i]), ALL(who[2 * i + 1]), who[i].begin());
  95.         }
  96.  
  97.         forn (i, 2 * tsz) if (i != 0)
  98.             vals[i] = segtree(sz(who[i]));
  99.     }
  100.  
  101.     pii query (int pos, int d, int u)
  102.     {
  103.         int l = lower_bound(ALL(who[pos]), mp(d, -inf)) - who[pos].begin();
  104.         int r = lower_bound(ALL(who[pos]), mp(u, -inf)) - who[pos].begin();
  105.         return vals[pos].getseg(l, r);
  106.     }
  107.  
  108.     pii rect (int l, int r, int d, int u)
  109.     {
  110.         pii ans(0, 0);
  111.         for (l += tsz, r += tsz; l < r; l >>= 1, r >>= 1)
  112.         {
  113.             if (l & 1)
  114.                 ans = max(ans, query(l++, d, u));
  115.             if (r & 1)
  116.                 ans = max(ans, query(--r, d, u));
  117.         }
  118.         return ans;
  119.     }
  120.  
  121.     void put_node (int v, int b, int what, int nid)
  122.     {
  123.         int pos = lower_bound(ALL(who[v]), mp(b, -inf)) - who[v].begin();
  124.         assert(pos != sz(who[v]) && who[v][pos].fst == b);
  125.         vals[v].put(pos, mp(what, nid));
  126.     }
  127.  
  128.     void put (int a, int b, int what, int nid)
  129.     {
  130.         put_node(a += tsz, b, what, nid);
  131.         for (a >>= 1; a > 0; a >>= 1)
  132.             put_node(a, b, what, nid);
  133.     }
  134. };
  135.  
  136. void solve (int n)
  137. {
  138.     vi a(n), b(n);
  139.     forn (i, n) cin >> a[i];
  140.     forn (i, n) cin >> b[i];
  141.     forn (i, n) a[i] = -a[i];
  142.     compr(a);
  143.     compr(b);
  144.  
  145.     segtree2d data(a, b);
  146.     const int A = *max_element(ALL(a));
  147.     const int B = *max_element(ALL(b));
  148.  
  149.     vi dp(n);
  150.     vi ptr(n, -1);
  151.     for (int i = n - 1; i >= 0; i--)
  152.     {
  153.         pii cur = data.rect(a[i], A + 1, b[i], B + 1);
  154.         dp[i] = cur.fst + 1;
  155.         ptr[i] = (cur.fst == 0 ? -1 : -cur.snd);
  156.         data.put(a[i], b[i], dp[i], -i);
  157.     }
  158.  
  159.     vi who;
  160.     const int cpos = max_element(ALL(dp)) - dp.begin();
  161.     int pos = cpos;
  162.     while (pos != -1)
  163.     {
  164.         who.pb(pos);
  165.         assert(0 <= pos && pos < n);
  166.         pos = ptr[pos];
  167.     }
  168.  
  169.     assert(dp[cpos] == sz(who));
  170.     cout << dp[cpos] << '\n';
  171.     forn (i, sz(who))
  172.         cout << who[i] + 1 << ' ';
  173.     cout << '\n';
  174. }
  175.  
  176. int main()
  177. {
  178.     ios_base::sync_with_stdio(false);
  179.     cin.tie(0);
  180.  
  181.     int n;
  182.     while (cin >> n)
  183.         solve(n);
  184. }
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
6
12 11 10 9 8 7
1 2 3 4 5 6
stdout
copy 
6
1 2 3 4 5 6
https://ideone.com/g2ZB4B
language:
C++ (gcc 8.3)
created:
7 years 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!