Submission #533193

#	Time	Username	Problem	Language	Result	Execution time	Memory
533193		exopeng	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	509 ms	44600 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
#define pii pair<int,int>
#define is insert
const long long INF = 1000000000;
const long long MOD = 1000000007;
const int MAXN=4e5;
//store test cases here
/*

find longest valid subsequence,
store list of LIS's with last height
for each new member, find max previous LIS
everything geq works
everything leq
factor in distance between indices so curr height can be up to a+dist*m

when inserting in set, insert in height-ix*m
when querying for valid ones, everything geq than curr-ix*m works
handle duplicate vals-




maintain segtree, c compress values

5 400
300 700 200 1000 500

3 300
700 1000 1300
*/
int n,m;
set<int> ix;
map<int,int> cp;
int t[4*MAXN];
int dp[MAXN];
int sum(int curr,int tl,int tr,int l,int r){
    if(l>r){
        return 0;
    }
    if(l==tl&&r==tr){
        return t[curr];
    }
    int mid=(tl+tr)/2;
    return max(sum(curr*2,tl,mid,l,min(r,mid)),sum(curr*2+1,mid+1,tr,max(l,mid+1),r));
}
void update(int curr,int tl,int tr,int pos,int val){
    if(tl==tr){
        t[curr]=val;
    }else{
        int mid=(tl+tr)/2;
        if(pos<=mid){
            update(curr*2,tl,mid,pos,val);
        }else{
            update(curr*2+1,mid+1,tr,pos,val);
        }
        t[curr]=max(t[curr*2],t[curr*2+1]);
    }
}
int a[MAXN];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    ix.is(0);
    //check long long 
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ix.is(a[i]-i*m);
        ix.is(m-i*m);
    }
    int tot=n;
    n=2*n+5;
    int ct=1;
    for(auto it=ix.begin();it!=ix.end();it++){
        cp[*it]=ct;
        ct++;
    }
    int mx=0;
    for(int i=1;i<=tot;i++){
        dp[i]=sum(1,1,n,cp[a[i]-i*m],n)+1;
        if(dp[i]==1&&a[i]-i*m>0){
            //check if can't even jump from height 0
            dp[i]=0;
            //update(1,1,n,cp[m-i*m],1);
        }else{
            update(1,1,n,cp[a[i]-i*m],dp[i]);
        }
        mx=max(mx,dp[i]);
    }
    //LIS has to contain height 0
    cout<<(tot-mx)<<"\n";
}
/* REMINDERS
 * CHECK ARRAY BOUNDS, HOW BIG ARRAY HAS TO BE
 * PLANNING!!!!!!!! Concrete plan before code
 * IF CAN'T FIGURE ANYTHING OUT, MAKE TEN TEST CASES TO EVALUATE ALL TYPES OF SCENARIOS, THEN CONSTRUCT SOLUTION TO FIT IT
 * IF CAN'T FIGURE ANYTHING OUT, MAKE TEN TEST CASES TO EVALUATE ALL TYPES OF SCENARIOS, THEN CONSTRUCT SOLUTION TO FIT IT
 * IF CAN'T FIGURE ANYTHING OUT, MAKE TEN TEST CASES TO EVALUATE ALL TYPES OF SCENARIOS, THEN CONSTRUCT SOLUTION TO FIT IT
 * NAIVE SOL FIRST TO CHECK AGAINST OPTIMIZED SOL
 * MOD OUT EVERY STEP
 * DON'T MAKE ASSUMPTIONS
 * DON'T OVERCOMPLICATE
 * CHECK INT VS LONG, IF YOU NEED TO STORE LARGE NUMBERS
 * CHECK CONSTRAINTS, C <= N <= F...
 * CHECK SPECIAL CASES, N = 1...
 * TO TEST TLE/MLE, PLUG IN MAX VALS ALLOWED AND SEE WHAT HAPPENS
 * ALSO CALCULATE BIG-O, OVERALL TIME COMPLEXITY
 * IF ALL ELSE FAILS, DO CASEWORK
 * compile with "g++ -std=c++11 filename.cpp" if using auto keyword
 */

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37