Concentric Tubes

#include <iostream>
#include <cmath>
#include <vector>
#include <cassert>
#include <algorithm>
#include <map>
using namespace std;
#define rep(i, a, b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;

const int N = 1<<18;

using seg_type = pii;
seg_type S[N*2];

void add(int i, seg_type x) {
  i |= N;
  S[i] = max(S[i], x);
  for (i /= 2; i >= 1; i /= 2) {
    S[i] = max(S[i*2], S[i*2+1]);
  }
}

seg_type Sget(int a, int b) {
  a |= N; b |= N;
  seg_type s = {0,0};
  while (a <= b) {
    if (a % 2 == 1) {
      s = max(s, S[a]);
      ++a;
    } if (b % 2 == 0) {
      s = max(s, S[b]);
      --b;
    }
    a /= 2; b /= 2;
  }
  return s;
}

int W[N*2];
tuple<int,int,int> R[N];
int ANS[N];

int main() {
  int n;
  cin >> n;
  rep(i,0,n) {
    int r;
    cin >> r;
    R[i] = {0,r,0};
    W[i] = r;
  }
  rep(i,0,n) {
    int r;
    cin >> r;
    R[i] = {r,get<1>(R[i]),i+1};
    W[n+i] = r;
  }
  // index
  sort(W,W+n*2);
  map<int,int> M;
  int w = 0;
  int index = 0;
  rep(i,0,n*2) {
    if (W[i] != w) {
      w = W[i];
      M[w] = index++;
    }
  }
  // sort
  rep(i,0,n) {
    auto [r2,r1,ind] = R[i];
    R[i] = {-M[r2], -M[r1], ind};
  }
  sort(R,R+n);
  // seg
  rep(i,0,n) {
    auto [r2,r1,rInd] = R[i];
    auto [val,ind] = Sget(-r2,n*2);
    ANS[rInd] = ind;
    add(-r1, {val+1,rInd});
  }
  // ans
  auto [val,ind] = Sget(0,n*2);
  cout << val << '\n';
  do {
    cout << ind << ' ';
    ind = ANS[ind];
  } while (ind);
  cout << '\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED