Submission #588759

#	Time	Username	Problem	Language	Result	Execution time	Memory
588759		jack715	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	177 ms	18452 KiB

triusis

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
#define int long long

using namespace std;

int n, m;
vector<int> nums, segtree, srt;

void update(int indx, int st, int end, int v, int val) {
    if (st == end) {
        segtree[indx] = val;
        return;
    }
    int mid = (st + end) / 2;
    if (v <= mid) 
        update(indx*2, st, mid, v, val);
    else 
        update(indx*2+1, mid+1, end, v, val);
    segtree[indx] = min(segtree[indx*2], segtree[indx*2+1]);
}

int query(int indx, int st, int end, int v) {
    // cout << indx << ' ' << st << ' ' << end << '\n';
    // cout << srt[st] << ' ' << srt[end] << '\n';
    if (srt[end] < v) return 1e9;
    if (srt[st] >= v) return segtree[indx];
    int mid = (st + end) / 2;
    return min(query(indx*2, st, mid, v), query(indx*2+1, mid+1, end, v));
}

signed main(){
    // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("tmp.in,", "r", stdin);
    // freopen("tmp.out", "w", stdout);

    cin >> n >> m;
    nums.resize(n+1), segtree.resize(n*4+10, 1e9);
    nums[0] = 0;
    vector<int> indx(n+1);
    vector<pair<int, int> > tmp;
    for (int i = 1; i <= n; i++) 
        cin >> nums[i];
    for (int i = 0; i <= n; i++)
        tmp.pb({nums[i]+(n-i)*m, i});
    sort(tmp.begin(), tmp.end());
    for (int i = 0; i <= n; i++) {
        srt.pb(tmp[i].ff);
        indx[tmp[i].ss] = i;
    }
    update(1, 0, n, indx[0], n);
    for (int i = 1; i <= n; i++) {
        int now = query(1, 0, n, nums[i]+(n-i)*m);
        // cout << now << ' ' << indx[i] << ", ";
        update(1, 0, n, indx[i], now-1);
    }
    // cout << '\n';

    int ans = query(1, 0, n, 0);
    cout << ans << '\n';
    return 0;
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

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