fork download
copy 
  1. // @NPL1210 2025-10-26
  2. #include <bits/stdc++.h>
  3. #define endl '\n'
  4. typedef int ll;
  5. using namespace std;
  6.  
  7. struct query {
  8.     ll l, r;
  9. };
  10. struct node {
  11.     ll order, u;
  12. };
  13. const ll MAXN = 3e5 + 5;
  14. const ll INF = 1e9;
  15. ll n, ans, a[MAXN], d[MAXN];
  16. query q[MAXN];
  17. vector<ll> g[MAXN], st[4 * MAXN];
  18. vector<node> order;
  19.  
  20. // Dung do thi dang cay phan doan
  21. void update(ll id, ll l, ll r, ll u, ll v, ll i) {
  22.     if (u > r || v < l) return;
  23.     if (u <= l && r <= v) {
  24.         st[id].push_back(i);
  25.         return;
  26.     }
  27.     ll mid = (l + r) >> 1;
  28.     update(id * 2, l, mid, u, v, i);
  29.     update(id * 2 + 1, mid + 1, r, u, v, i);
  30. }
  31.  
  32. // Lay moi doan co chua pos
  33. void get(ll id, ll l, ll r, ll pos, vector<ll> &out) {
  34.     if (pos < l || pos > r) return;
  35.     for (ll x : st[id]) out.push_back(x);
  36.     // Moi pos minh chi lay mot lan thoi nen co the clear tranh lap nhieu lan TLE
  37.     st[id].clear();
  38.     if (l == r) return;
  39.     ll mid = (l + r) >> 1;
  40.     if (pos <= mid) get(id * 2, l, mid, pos, out);
  41.     else get(id * 2 + 1, mid + 1, r, pos, out);
  42. }
  43.  
  44. void sub3() {
  45.     for (ll i = 1; i <= n; i++) {
  46.         update(1, 1, n, q[i].l, q[i].r, i);
  47.     }
  48.     vector<pair<ll,ll>> order;
  49.     for (ll i = 1; i <= n; ++i) order.push_back({a[i], i});
  50.     sort(order.begin(), order.end(), greater<pair<ll,ll>>());
  51.     for (ll i = 1; i <= n; ++i) d[i] = INF;
  52.     queue<ll> qu;
  53.     ll pos = 0;
  54.     while (pos < n) {
  55.         ll cur = order[pos].first;
  56.         vector<ll> src;
  57.         while (pos < n && order[pos].first == cur) {
  58.             ll i = order[pos].second;
  59.             if (d[i] == INF) {
  60.                 d[i] = 0;
  61.                 src.push_back(i);
  62.             }
  63.             pos++;
  64.         }
  65.         for (ll s : src) qu.push(s);
  66.         while (!qu.empty()) {
  67.             ll u = qu.front(); qu.pop();
  68.             // Lay tat ca i sao cho u thuoc [L_i, R_i]
  69.             vector<ll> got;
  70.             get(1, 1, n, u, got);
  71.             for (ll i : got) {
  72.                 if (d[i] == INF) {
  73.                     d[i] = d[u] + 1;
  74.                     qu.push(i);
  75.                 }
  76.             }
  77.         }
  78.     }
  79.     for (ll i = 1; i <= n; i++) if (d[i] != INF) ans = max(ans, d[i]);
  80.     cout << ans + 1 << endl;
  81. }
  82.  
  83. void sol() {
  84.     cin >> n;
  85.     for (ll i = 1; i <= n; i++) cin >> a[i];
  86.     for (ll i = 1; i <= n; i++) {
  87.         cin >> q[i].l >> q[i].r;
  88.     }
  89.     sub3();
  90. }
  91.  
  92. int main() {
  93.     ios::sync_with_stdio(0);
  94.     cin.tie(0);
  95.  
  96.     freopen("INCOME.INP", "r", stdin);
  97.     freopen("INCOME.OUT", "w", stdout);
  98.  
  99.     sol();
  100.  
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0.01s 39728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qCLGBA
language:
C++14 (gcc 8.3)
created:
6 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!