Submission #967319

#	Time	Username	Problem	Language	Result	Execution time	Memory
967319		Keshav211	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	102 ms	29640 KiB

triusis

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <chrono>
#include <string>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <climits>
#include <bitset>
#define all(x) (x).begin(), (x).end()
#define vec(n) vll arr(n);
#define printarr(arr) for(auto i:arr){cout<<i<<" ";}cout<<endl;
#define printdict(dict) for(auto i:dict)cout<<i.first<<": "<<i.second<<endl;
#define printadj(adj) for(ll i=0;i<n;i++){if(!adj[i].empty()){cout<<i<<": ";printarr(adj[i])}}
#define read(arr); for(ll i=0;i<arr.size();i++) cin>>arr[i];
#define readundirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);adj[b].pb(a);}
#define readdirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);}
#define readfunc(n) for(ll i=0;i<n;i++){ll a;cin>>a;a--;func_adj[i]=a;}
#define grid(n,m) for (ll i=1;i<=n;i++){for (ll j=1;j<=m;j++) cin>>graph[i][j];}
#define vll vector<ll>
#define sll set<ll>
#define msll multiset<ll>
#define qll queue<ll>
#define pll pair<ll,ll>
#define str string
#define pb push_back
#define ll long long
#define ld long double
using namespace std;
const str alph="abcdefghijklmnopqrstuvwxyz";
const str capalph="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll inf=5e5+1;
const ll graph_size=1000;
const ll mod=1e9+7;
const ld pi=3.141592653589793238462643383279502884197;
const ll large=1e18;
const ll small=-1e18;
vll adj[inf];
bool visited[inf];
ll level[inf];
ll parent[inf];
char graph[graph_size+2][graph_size+2];
vector<pll> directions={{0,-1},{-1,0},{1,0},{0,1}};
bool floodfill_visited[graph_size+2][graph_size+2];
ll floodfill_level[graph_size+2][graph_size+2];
pll floodfill_parent[graph_size+2][graph_size+2];
// Fast Input/Output
void fastio(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
}
// File Input/Output
str fileio(const string&filePath=__FILE__){
    size_t lastSlash=filePath.find_last_of('/');
    size_t lastDot=filePath.rfind('.');
    return filePath.substr(lastSlash+1,lastDot-lastSlash-1);
}
// For Yes Or No Problems
str yes_or_no(bool test){
    if (test){
       return "YES";
    }
    return "NO";
}
ll n,m,q;
// Coordinate Compression
vll compress(vll arr){
    map<ll,ll> count;
    for (auto i:arr){
        count[i]++;
    }
    ll curr=0;
    for (auto i:count){
        count[i.first]=curr;
        curr++;
    }
    for (ll i=0;i<arr.size();i++){
        arr[i]=count[arr[i]];
    }
    return arr;
}
// Segment Trees
struct segTree{
    vll tree;
    vll arr;
    const ll start_val=0;
    segTree(ll n){
        ll val=ceil(log2(n));
        n=1<<val;
        tree=vll(2*n,start_val);
        arr=vll(n,start_val);
    }
    ll merge(ll a,ll b){
        ll ans=max(a,b);
        return ans;
    }
    void add(ll ind,ll val){
        arr[ind]+=val;
        ind+=arr.size();
        tree[ind]+=val;
        while(ind/2>0){
            tree[ind/2]=merge(tree[ind],tree[ind^1]);
            ind/=2;
        }
    }
    void update(ll ind,ll val){
        add(ind,val-arr[ind]);
    }
    ll query(ll a,ll b){
        a+=arr.size();
        b+=arr.size();
        ll ans=start_val;
        while(a<=b){
            if(a%2==1){
                ans=merge(ans,tree[a]);
                a++;
            }
            if(b%2==0){
                ans=merge(ans,tree[b]);
                b--;
            }
            a/=2;
            b/=2;
        }
        return ans;
    }
};
int main(){
    // auto start_time=chrono::steady_clock::now();
    fastio();
    // str filename=fileio();
    // ifstream cin(filename+".in");
    // ofstream cout(filename+".out");
    ll t=1;
    // cin>>t;
    while (t--){
        cin>>n>>m;
        vll arr;
        for (ll i=0;i<n;i++){
            ll a;
            cin>>a;
            arr.pb(m*(i+1)-a);
            if (arr.back()<0){
                arr.pop_back();
            }
        }
        arr=compress(arr);
        segTree segtree(n);
        ll ans=0;
        for (auto i:arr){
            ll curr=segtree.query(0,i)+1;
            ans=max(ans,curr);
            segtree.update(i,max(segtree.arr[i],curr));
        }
        ans=n-ans;
        cout<<ans<<"\n";
    }
    // auto end_time=chrono::steady_clock::now();
    // auto elapsed_time=chrono::duration_cast<chrono::milliseconds>(end_time-start_time);
    // cout<<"Elapsed time: "<<elapsed_time.count()<<" milliseconds\n";
}

Compilation message (stderr)

triusis.cpp: In function 'std::vector<long long int> compress(std::vector<long long int>)':
triusis.cpp:84:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (ll i=0;i<arr.size();i++){
      |                 ~^~~~~~~~~~~

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