제출 #1108550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1108550		Plot_Twist	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	1 ms	336 KiB

triusis

#include<bits/stdc++.h>
#include<chrono>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

using namespace std;
using namespace chrono;
#define ll long long
#define vl vector<long long>
#define endl '\n'
const int MOD = 1e9 + 7;
void inputv(vl &v) {for(int i = 0; i < (ll)v.size(); i++) cin>>v[i];}
void printv(vl v) {for(auto i : v) cout<<i<<" ";cout<<endl;}


#define int long long

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;


template <typename T>
class SegTree {
public:
    vector <T> tree;

    SegTree(int size) {
        tree.resize(size, 0);
    }

    T func(T a, T b) {
        return max(a, b); // Segment tree for the sum
        // return min(a, b); // Segment tree for the minimum
    }

    void update(int node, int start, int end, int pos, T val) {
        if(start == end) {
            tree[node] = val; // Assign value here.
        } else {
            int mid = (start + end)/2;
            if(pos <= mid) {
                update(node*2, start, mid, pos, val);
            } else {
                update(node*2 + 1, mid + 1, end, pos, val);
            }
            tree[node] = func(tree[node*2], tree[node*2 + 1]);
        }
    }

    T query(int node, int start, int end, int l, int r) {
        if(l > r) {
            return 0; // Return appropriate value, for example INF for minimum.
        }
        if(l == start && r == end) {
            return tree[node];
        }
        int mid = (start + end)/2;
        return func(query(node*2, start, mid, l, min(mid, r)), query(node*2 + 1, mid + 1, end, max(l, mid + 1), r));
    }
};

signed main() {

    ios::sync_with_stdio(false); cin.tie(NULL);
    int ts = 1;

    while(ts--) {
        int n,m;
        cin>>n>>m;
        vl arr(n);
        inputv(arr);
        map<int,int>mp;
        int ans = -1;
        int current = 0;
        for(int i = 0; i < n; i++) {
            if(arr[i] > current + m) {
                arr[i] = current+m;
                current = arr[i];
            }
            else {
                ans = i;
                break;
            }
        }
        if(ans==-1) {
            cout<<n<<endl;
            continue;
        }
        for(int i = ans; i< n; i++) mp[arr[i]];
        int temp = 0;
        for(auto &[a,b] : mp) b = temp++;

        SegTree<int>seg(temp<<2);
        seg.update(1,0,temp-1, mp[arr[ans]], 1);
        int ans_ = 1;
        for(int i = ans+1; i < n; i++) {
            int curr = mp[arr[i]];
            auto it = mp.lower_bound(arr[i] - m);
            int lq = (*it).second;
            int maxi = seg.query(1,0,temp-1,lq,temp-1);
            ans_ = max(ans_, maxi+1);
            seg.update(1,0,temp-1, curr, maxi+1);
        }
        cout<<n-ans_<<endl;
    }

    
}

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