Submission #549786

#	Time	Username	Problem	Language	Result	Execution time	Memory
549786		Vladth11	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	164 ms	17512 KiB

triusis

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 200005;
const ll VMAX = 26;
const ll INF = (1LL << 55);
const ll MOD = 90000000000000001;
const ll BLOCK = 1000000;
const ll base = 1000000001;
const ll nr_of_bits = 18;

ll v[NMAX];
int dp[NMAX];
vector <int> nrm;
unordered_map <int, int> mp;
int aint[NMAX * 4];

void update(int node, int st, int dr, int a, int b){
    if(st == dr){
        aint[node] = min(aint[node], b);
        return;
    }
    int mid = (st + dr) / 2;
    if(a <= mid)
        update(node * 2, st, mid, a, b);
    else
        update(node * 2 + 1, mid + 1, dr, a, b);
    aint[node] = min(aint[node * 2], aint[node * 2 + 1]);
}

int query(int node, int st, int dr, int a, int b){
    if(a <= st && dr <= b)
        return aint[node];
    int mid = (st + dr) / 2;
    int minim = 2e9;
    if(a <= mid)
        minim = min(minim, query(node * 2, st, mid, a, b));
    if(b > mid)
        minim = min(minim, query(node * 2 + 1, mid + 1, dr, a, b));
    return minim;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i, m;
    for(i = 1; i < NMAX * 4; i++)
        aint[i] = 2e9;
    cin >> n >> m;
    nrm.push_back(0);
    nrm.push_back(-2e9);
    for(i = 2; i <= n + 1; i++){
        cin >> v[i];
        v[i] -= m * (i - 1);
        nrm.push_back(v[i]);
    }
    sort(nrm.begin(), nrm.end());
    int cnt = 0;
    for(i = 0; i < nrm.size(); i++){
        if(i == 0 || nrm[i] != nrm[i - 1])
            cnt++;
        mp[nrm[i]] = cnt;
    }
    for(i = 1; i <= n + 1; i++)
        v[i] = mp[v[i]];
    n += 2;
    v[n] = 1; /// numar artificial
    int minim = 0;
    for(i = 1; i <= n; i++){
        dp[i] = i - 1 + query(1, 1, NMAX, v[i], NMAX);
        if(i == 1)
            dp[i] = 0;
        update(1, 1, NMAX, v[i], dp[i] - i);
    }
    cout << dp[n];
    return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(i = 0; i < nrm.size(); i++){
      |                ~~^~~~~~~~~~~~
triusis.cpp:74:9: warning: unused variable 'minim' [-Wunused-variable]
   74 |     int minim = 0;
      |         ^~~~~

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