//In the name of God
#include<bits/stdc++.h>
/*MHN*/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T>
using ordered_set = tree< T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef int lli;
typedef long double ld;
typedef pair<lli,lli> pii;
typedef pair<pii,pii> piiii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=1e6+10;
const lli mod=1e9+7;//998244353;//1e9+9
lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;}
lli modinv(lli x){return power(x,mod-2);}
lli divide(lli x,lli y){return ((x%mod) * modinv(y))%mod;}
#define all(v) v.begin(),v.end()
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define minheap priority_queue<pair<lli,pii>, std::vector<pair<lli,pii>>, std::greater<pair<lli,pii>>>
#define set_preci(x) cout << fixed << setprecision(x);
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define SUM(v) accumulate(v.begin(),v.end(), 0LL)
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--)
#define BN(l,a) while(l){a.PB(l%2);l/=2;}
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define sep " "
lli tmp;
struct Fenwick{
ve bit;
lli n;
void build(lli sz){
FOR(i,sz+3)bit.PB(0);
n = sz;
}
void update(lli i,lli x){
if(i == 0){bit[0] = max(bit[0],x);return;}
for(; i <= n; i += i&(-i))
bit[i] = max(bit[i],x);
}
lli get(lli i){
lli ans = bit[0];
for(; i > 0; i -= (-i)&i)
ans = max(ans,bit[i]);
return ans;
}
};
lli n;
pii Q[N];
lli pos[N],A[N],dp[N];
struct Node{
ve ozv;
Fenwick fen;
};
Node seg[N*4];
Node DEF;
Node Merge(Node a,Node b){
Node res;
for(auto i : a.ozv)res.ozv.PB(i);
for(auto i : b.ozv)res.ozv.PB(i);
sort(all(res.ozv));
return res;
}
Node Tak(lli p){
Node res;
res.ozv.PB(A[p]);
res.fen.build(1);
return res;
}
void build(lli l = 1,lli r = n+1,lli id = 1){
if(r-l == 1){
seg[id] = Tak(l);
return;
}
lli mid = (l+r)/2;
build(l,mid,id*2);
build(mid,r,id*2+1);
seg[id] = Merge(seg[id*2],seg[id*2+1]);
seg[id].fen.build(seg[id].ozv.size());
}
void Upd(lli l,lli r,lli p,lli id){
if(r<=p || l>p)return;
lli in = lb(all(seg[id].ozv),A[p]) - seg[id].ozv.begin();
seg[id].fen.update(in,dp[p]);
if(r-l == 1){
return;
}
lli mid = (l+r)/2;
Upd(l,mid,p,id*2);
Upd(mid,r,p,id*2+1);
}
lli Get(lli l,lli r,lli st,lli en,lli num,lli id){
if(l >= en || r <= st)return 0;
if(l>=st && r<=en){
lli in = lb(all(seg[id].ozv),num) - seg[id].ozv.begin();
in --;
if(in >= 0)return seg[id].fen.get(in);
return 0;
}
lli mid = (l+r)/2;
lli res = max(Get(l,mid,st,en,num,id*2) ,Get(mid,r,st,en,num,id*2+1) );
return res;
}
ve mak[N],rmak[N];
bool came[N];
void input(){
cin>>n;
ordered_set<lli> mos;
FORS(i,n){
cin>>Q[i].fi>>Q[i].se;
mos.insert(i);
}
for(lli i = n; i > 0; i --){
pos[i] = *mos.find_by_order(Q[i].fi-1);
A[pos[i]] = Q[i].se;
mak[Q[i].se].PB(pos[i]);
for(lli j = Q[i].se; j > 0; j--)
rmak[j].PB(pos[i]);
mos.erase(mos.find(pos[i]));
}
FOR(i,N)sort(all(mak[i]));
FOR(i,N)sort(all(rmak[i]));
}
int main(){
migmig;
input();
build();
lli ans = 0;
FORS(i,n){
lli in = Q[i].fi,x = Q[i].se;
in = pos[i];
came[in] =1;
dp[in]=1;
for(lli j = x-1; j > 0 ; j--){
for(auto k : mak[j]){
if(k > in)continue;
dp[in] = max(dp[in],dp[k] + 1);
ans=max(ans,dp[k]);
}
}
Upd(1,n+1,in,1);
for(auto j : rmak[x+1]){
if(came[j] == 0)continue;
lli la = dp[j];
dp[j] = max(dp[j],1+Get(1,n+1,1,j,A[j],1));
ans=max(ans,dp[j]);
if(dp[j] != la)
Upd(1,n+1,j,1);
}
ans = max(ans,dp[in]);
cout<<ans<<endl;
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
