제출 #946754

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946754		KK_1729	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	98 ms	26820 KiB

triusis

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";
    cout << endl;
}

int max(int x, int y){
    if (x > y) return x;
    else return y;
}

vector<int> tree;
vector<int> a;
int query(int l, int r, int pos, int ql, int qr){
    if (ql > r || l > qr) { //no intersection case
        return 0;
    }
    if (ql <= l && r <= qr) { //total intersection case
        // cout << tree[pos] << pos << endl;
        return tree[pos];
    }
 
 
    int mid = (l+r)/2;
    return max(query(l, mid, pos*2, ql, qr), query(mid+1, r, pos*2+1, ql, qr));
}
void update(int l, int r, int pos, int qval, int qpos){
    // cout << l << r << endl;
    if (l == r){
        tree[pos]  = qval;
        return;
    }
    int mid = (l+r)/2;
    if (qpos <= mid){
        update(l, mid, pos*2, qval, qpos);
    }else{
        update(mid+1, r, pos*2+1, qval, qpos);
    }
    tree[pos] = max(tree[pos*2], tree[pos*2+1]);
}
bool compare(int x, int y){
    if (a[x] < a[y]) return true;
    if (a[x] == a[y]){
        if (x < y) return true;
    }
    return false;
}
int lis(vector<int> u){
    a = u;
    int n = a.size();
    int N = n;
    while (__builtin_popcount(N) != 1){
        N++;
    }
    tree.resize(2*N);
    
 
    vector<int> p(n);
    FOR(i,0,n) p[i] = i;
    sort(all(p), compare);
    vector<vector<int>> components;
    vector<int> component;
    int current = 1;
    FOR(i,0,n){
        if (i == 0){
            component.pb(p[i]);
        }else{
            if (a[p[i]] == a[p[i-1]]) component.pb(p[i]);
            else{
                components.pb(component);
                component = {p[i]};
            }
        }
    }
 if (component.size()) components.pb(component);
    // printVector(p);
    for (auto component: components){
        vector<int> o(component.size());
        int m = component.size();
        FOR(i,0,m){
            o[i] = query(0, N-1, 1, 0, component[i]);
            update(0, N-1, 1, o[i]+1, component[i]);
        }
        
    }
    // printVector(tree);
    return query(0, N-1, 1, 0, n);
}

void solve(){
    int n, m; cin >> n >> m;
    vector<int> a(n+1);
    FOR(i,1,n+1) cin >> a[i];

    vector<int> b(n+1);
    FOR(i,1,n+1) b[i] = m*i-a[i];

    // printVector(b);
    vector<int> k;
    FOR(i,1,n+1){
        if (b[i]>= 0) k.pb(b[i]);
    }
    // printVector(k);
    cout << n-lis(k) << endl;
    // printVector(dp);
}
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", stdin)
    int t = 1; // cin >> t;
    while (t--) solve();
}

컴파일 시 표준 에러 (stderr) 메시지

triusis.cpp: In function 'long long int lis(std::vector<long long int>)':
triusis.cpp:71:9: warning: unused variable 'current' [-Wunused-variable]
   71 |     int current = 1;
      |         ^~~~~~~

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