#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
// #ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 1e6 + 5, sq = 2000, lg = 20, inf = ll(1e18) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
int fen[maxn], n, pos[maxn], val[maxn], dp[maxn], tmp[maxn];
set<int> val_pos[sq], place[sq];
int ptr, stk[maxn], en;
int main(){ IOS();
cin >> n;
stk[0] = -1;
rep(i,1,n+1){
fen[i] = i&-i;
stk[i] = -1;
}
// map<int, int> cmp;
rep(i,0,n){
cin >> pos[i] >> tmp[i];
// cmp[tmp[i]] = 0;
}
// int id = 0;
// for(auto&c: cmp) c.ss = id++;
vector<bool> is(n + 1);
per(i,n-1,0) {
int ps = 0, cr = pos[i];
per(i,lg-1,0){
if((ps|(1<<i)) < n && fen[ps|(1<<i)] < cr){
ps |= 1<<i;
cr -= fen[ps];
}
}
ps++;
assert(!is[ps]);
is[ps] = true;
// er(nw);
val[ps] = cmp[tmp[i]];
pos[i] = ps;
for(; ps < n + 1; ps += ps&-ps) fen[ps]--;
}
// rep(i,0,n) er(pos[i], val[i]);
int ans = 1;
rep(i,0,n){
int p = pos[i], v = val[pos[i]];
dp[p] = 1;
rep(j,0,v){
auto it = lower_bound(all(val_pos[j]), p);
if(it != begin(val_pos[j])){
dp[p] = max(dp[p], dp[*prev(it)] + 1);
// er(i, j);
}
}
// er(i, dp[p]);
place[dp[p]].insert(p);
val_pos[v].insert(p);
// auto bg = place[dp[p]].upper_bound(p), en = bg;
// for(; en != end(place[dp[pos[i]]]) && val[*en] > v; en++) dp[*en]++, ans = max(ans, dp[p] + 1), er(i, *en, val[*en], v);
// place[dp[p] + 1].insert(bg, en);
// place[dp[p]].erase(bg, en);
// rep(i,1,5){
// cerr << i << ":" << endl;
// for(int c: place[i]) cerr << c << ' ';
// cerr << endl;
// }
// cerr << "_____" << endl;
// vector<int> stk{p};
stk[en++] = p;
// stk.reserve(100);
while(ptr < en){
int r = stk[ptr]; ptr++;
ans = max(ans, dp[r]);
auto it = place[dp[r]].lower_bound(r);
for(it++; it != end(place[dp[r]]) && val[*it] > val[r];){
dp[*it]++;
stk[en++] = *it;
place[dp[r] + 1].insert(*it);
it++;
place[dp[r]].erase(prev(it));
}
}
cout << ans << '\n';
}
return 0-0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:58:21: error: 'cmp' was not declared in this scope; did you mean 'tmp'?
58 | val[ps] = cmp[tmp[i]];
| ^~~
| tmp
