Submission #796916

#	Time	Username	Problem	Language	Result	Execution time	Memory
796916		ashcomp	LIS (INOI20_lis)	C++14	100 / 100	1142 ms	98920 KiB

Main

#include<bits/stdc++.h>

using namespace std;
 
#define all(x) x.begin() , x.end()
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pb push_back
#define qb pop_back
#define F first
#define S second
#define wall cerr<<"--------------------------------------"<<endl
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#pragma GCC optimize("Ofast")
 
typedef long long ll;
typedef double db;

const ll INF = 1e9;
const ll maxn = 2e6 + 10;
const ll SQRT = 2e3 + 10;

int n , Ps[maxn] , Vl[maxn] , a[maxn] , T[maxn];

int Lz[maxn<<2] , Ar[maxn<<2];
void Build(int tl=1 , int tr=n , int v=1)
{
        if(tl==tr){
                Ar[v] = tl;
                return;
        }
        int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
        Build(tl,mid,ml); Build(mid+1,tr,mr);
        Ar[v] = max(Ar[ml],Ar[mr]);
}
inline void Shift(int tl , int tr , int v)
{
        int ml=(v<<1) , mr=(v<<1)|1;
        Ar[v] += Lz[v];
        Ar[v] = max(0,Ar[v]);
        if(tl!=tr){
                Lz[ml] += Lz[v];
                Lz[mr] += Lz[v];
        }
        Lz[v] = 0;
}
void Upd(int l , int r , int tl=1 , int tr=n , int v=1)
{
        Shift(tl,tr,v);
        if(l>r)return;
        if(l==tl && r==tr){
                Lz[v] --;
                Shift(tl,tr,v);
                return;
        }
        int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
        Upd(l,min(r,mid),tl,mid,ml);
        Upd(max(l,mid+1),r,mid+1,tr,mr);
        Ar[v] = max(Ar[ml],Ar[mr]);
}
void Change(int pos , int tl=1 , int tr=n , int v=1)
{
        Shift(tl,tr,v);
        if(tl==tr){
                Ar[v] = 0;
                return;
        }
        int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
        if(pos<=mid)Change(pos,tl,mid,ml);
        else Change(pos,mid+1,tr,mr);
        Ar[v] = max(Ar[ml],Ar[mr]);
}
int Find(int val , int tl=1 , int tr=n , int v=1)
{
        Shift(tl,tr,v);
        if(tl==tr){
                return tl;
        }
        int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
        Shift(tl,mid,ml); Shift(mid+1,tr,mr);
        if(Ar[ml]>=val){
                return Find(val,tl,mid,ml);
        }else{
                return Find(val,mid+1,tr,mr);
        }
}
// just to find the array
/******/

struct segment
{
        int seg[SQRT<<2];
        void build(int tl=1 , int tr=SQRT , int v=1)
        {
                seg[v] = INF;
                if(tl==tr){
                        return;
                }
                int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
                build(tl,mid,ml); build(mid+1,tr,mr);
        }
        void upd(int pos , int val , int tl=1 , int tr=SQRT , int v=1)
        {
                if(tl==tr){
                        seg[v] = min(val,seg[v]);
                        return;
                }
                int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
                if(pos<=mid)upd(pos , val , tl , mid , ml);
                else upd(pos , val , mid+1 , tr , mr);
                seg[v] = min(seg[ml] , seg[mr]);
        }
        int ask(int l , int r , int tl=1 , int tr=SQRT , int v=1)
        {
                if(l>r)return INF;
                if(l==tl && r==tr){
                        return seg[v];
                }
                int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
                return min(ask(l,min(r,mid),tl,mid,ml) , 
                        ask(max(l,mid+1),r,mid+1,tr,mr));
        }
        int node()
        {
                return seg[1];
        }
}seg[SQRT+1];

int main()
{
        ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
        cin>>n;
        for(int i=1; i<=n; i++){
                cin>>Ps[i]>>Vl[i];
        }
        Build();
        for(int i=n; i>=1; i--){
                int pos = Find(Ps[i]);
                Change(pos);
                Upd(pos+1,n);
                a[pos] = Vl[i];
                T[pos] = i;
        }
        // we found the array
        /***/
        vector<pll> ve;
        for(int i=1; i<=n; i++){
                ve.push_back({a[i],i});
        }
        sort(all(ve));
        int res = 1;
        a[ve[0].S] = 1;
        for(int i=1; i<n; i++){
                if(ve[i].F != ve[i-1].F){
                        res++;
                }
                a[ve[i].S] = res;
        }
        // comperes
        /**/
        for(int i=1; i<=SQRT; i++){
                seg[i].build();
        }
        for(int i=1; i<=n; i++){
                seg[1].upd(a[i],T[i]);
                for(int j=2; j<=a[i]; j++){
                        int x = seg[j-1].ask(1,a[i]-1);
                        x = max(x , T[i]);
                        seg[j].upd(a[i],x);
                }
        }
        for(int i=1; i<=n; i++)a[i]=0;
        for(int i=1; i<=SQRT; i++){
                int x = seg[i].node();
                //cout<<x<<"\n";
                if(x==INF)continue;
                a[x] = i;
        }
        for(int i=1; i<=n; i++){
                a[i] = max(a[i-1],a[i]);
        }
        for(int i=1; i<=n; i++)cout<<a[i]<<"\n";
        return 0;
}
/*
6
1 7
2 10
2 11
2 8
4 10
1 2
*/
/*
ans =
1
2
2
3
3
4
*/
/*
by
          _____                    _____                    _____                    _____                  
         /\    \                  /\    \                  /\    \                  /\    \                 
        /::\    \                /::\    \                /::\____\                /::\    \                
       /::::\    \              /::::\    \              /:::/    /                \:::\    \               
      /::::::\    \            /::::::\    \            /:::/    /                  \:::\    \              
     /:::/\:::\    \          /:::/\:::\    \          /:::/    /                    \:::\    \             
    /:::/__\:::\    \        /:::/__\:::\    \        /:::/____/                      \:::\    \            
   /::::\   \:::\    \       \:::\   \:::\    \      /::::\    \                      /::::\    \           
  /::::::\   \:::\    \    ___\:::\   \:::\    \    /::::::\    \   _____    ____    /::::::\    \          
 /:::/\:::\   \:::\    \  /\   \:::\   \:::\    \  /:::/\:::\    \ /\    \  /\   \  /:::/\:::\    \         
/:::/  \:::\   \:::\____\/::\   \:::\   \:::\____\/:::/  \:::\    /::\____\/::\   \/:::/  \:::\____\        
\::/    \:::\  /:::/    /\:::\   \:::\   \::/    /\::/    \:::\  /:::/    /\:::\  /:::/    \::/    /        
 \/____/ \:::\/:::/    /  \:::\   \:::\   \/____/  \/____/ \:::\/:::/    /  \:::\/:::/    / \/____/         
          \::::::/    /    \:::\   \:::\    \               \::::::/    /    \::::::/    /                  
           \::::/    /      \:::\   \:::\____\               \::::/    /      \::::/____/                   
           /:::/    /        \:::\  /:::/    /               /:::/    /        \:::\    \                   
          /:::/    /          \:::\/:::/    /               /:::/    /          \:::\    \                  
         /:::/    /            \::::::/    /               /:::/    /            \:::\    \                 
        /:::/    /              \::::/    /               /:::/    /              \:::\____\                
        \::/    /                \::/    /                \::/    /                \::/    /                
         \/____/                  \/____/                  \/____/                  \/____/                 
                                                                                                            
*/
//NOGHRE SHODANAM BAD NIST :_)

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