Submission #483352

#	Time	Username	Problem	Language	Result	Execution time	Memory
483352		Olympia	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	171 ms	27172 KiB

triusis

#include <cmath>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <cassert>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
using namespace std;
#define ll long long
template<class T> struct Seg { // comb(ID,b) = b
    const T ID = 0; T comb(T a, T b) { return max(a,b); }
    int n; vector<T> seg;
    void init(int _n) { n = _n; seg.assign(2*n,ID); }
    void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
    void upd(int p, T val) { // set val at position p
        seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
    T query(int l, int r) {	// sum on interval [l, r]
        T ra = ID, rb = ID;
        for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
            if (l&1) ra = comb(ra,seg[l++]);
            if (r&1) rb = comb(seg[--r],rb);
        }
        return comb(ra,rb);
    }
};
int lis (vector<ll> v) {
    int n = v.size();
    Seg<int> st;
    st.init(v.size() + 2);
    vector<int> dp(v.size());
    set<int> mySet;
    for (int i = 0; i < v.size(); i++) {
        dp[i] = 0;
        mySet.insert(v[i]);
    }
    map<int,int> myMap;
    int cntr = 0;
    for (int i: mySet) {
        myMap[i] = ++cntr;
    }
    for (int i = 0; i < n; i++) {
        v[i] = myMap[v[i]];
    }
    for (int i = 0; i < n; i++) {
        st.upd(v[i], st.query(0, v[i]) + 1);
    }
    return st.query(0, n);
}
int main() {
    int n;
    cin >> n;
    int m;
    cin >> m;
    vector<ll> v(n + 1);
    v[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        v[i] = m * i - v[i];
    }
    vector<ll> vec;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] >= 0) {
            vec.push_back(v[i]);
        }
    }
    cout << n + 1 - lis(vec);
}

Compilation message (stderr)

triusis.cpp: In function 'int lis(std::vector<long long int>)':
triusis.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
triusis.cpp: In function 'int main()':
triusis.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

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