Submission #1259107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259107		mohammadsam	LIS (INOI20_lis)	C++20	100 / 100	2125 ms	213808 KiB

Main

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb            push_back
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 1e6 + 10,SQ=320,LOG=22;
const ll inf = 2e9 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int   q;
int x[N],p[N];
int fen[N];
int pos[N];
int arr[N];
void add(int i,int v){
    for(;i<N;i+=-i&i) fen[i] += v;
}
int search(int k){
    int now = 0;
    int sum = 0;
    for(int j =LOG-1;j >= 0;j--){
        if(now + (1<<j) <= q && sum + fen[now + (1<<j)] < k){
            sum += fen[now + (1<<j)];
            now += (1<<j);
        }
    }
    return now + 1;
}
int dp[N];
set<int> id[N],ind[N];
int mx = 0;
void dfs(int u){
    mx = max(mx,dp[u]);
    auto it = id[dp[u]].upper_bound(u);
    vector<int> vec;
    while(it != id[dp[u]].end() && arr[*it] > arr[u]){
        dp[*it] ++;
        id[dp[*it]].insert(*it);
        vec.pb(*it);
        it = id[dp[u]].erase(it);
    }
    for(auto h : vec) dfs(h);
}
int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    cin >> q;
    for(int i =1 ;i <= q;i++){
        cin >> p[i] >> x[i];
    }
    for(int i = 1;i <= q;i++) add(i,1);
    for(int i = q;i >= 1;i--){
        pos[i] = search(p[i]);
        arr[pos[i]] = x[i];
        add(pos[i],-1);
    }
    for(int i = 1;i <= q;i++){
        dp[pos[i]] = 1;
        mx = max(mx,1);
        for(int j = 1 ;j < x[i];j++){
            auto it = ind[j].lower_bound(pos[i]);
            if(it != ind[j].begin()){
                it--;
                dp[pos[i]] = max(dp[pos[i]],dp[*it] + 1);
                mx = max(mx,dp[pos[i]]);
            }
        }
        ind[x[i]].insert(pos[i]);
        id[dp[pos[i]]].insert(pos[i]);
        dfs(pos[i]);
        cout << mx << endl;
    }
    

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80