Submission #248564

#	Time	Username	Problem	Language	Result	Execution time	Memory
248564		Sprdalo	Global Warming (CEOI18_glo)	C++17	100 / 100	535 ms	38296 KiB

glo

#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

template<int MAXN>
struct segtr{
    //To change the purpose of the segtree just redefine the operators
    struct node{
        int x;
        node(int x = 0) : x(x) {}
        node& operator+= (const node& other){
            x = max(x, other.x);
            return *this;
        }
        node operator+ (const node& other){
            node tmp = *this;
            return tmp += other;
        }
    };
    
    node a[2*MAXN];
    
    //Initialize the array
    void init(){
        for(int i = 1; i <= MAXN; ++i){
            a[i+MAXN-1] = node{};
        }
        for(int i = MAXN-1; i > 0; --i){
            a[i] = a[2*i] + a[2*i+1];
        }
    }
    
    //Sets the node and updates the tree
    void set(int pos, node val){
        pos += MAXN-1;
        a[pos] = val;
        
        while(pos > 1){
            pos /= 2;
            a[pos] = a[2*pos] + a[2*pos+1];
        }
    }
    inline void add(int pos, node val){ //Just forwards to set
        set(pos, node{a[pos+MAXN-1]+val});
    }
    
    //Gets the range query
    node get(int l, int r, int pos = 1, int rl = 1, int rr = MAXN){
        if(r < rl || rr < l){ return node{}; }
        if(l <= rl && rr <= r){ return a[pos]; }
        
        int rm = (rl+rr)/2;
        return get(l, r, 2*pos, rl, rm) + get(l, r, 2*pos+1, rm+1, rr);
    }
    
};
segtr<131072*2> drvo;

vi a, lds, c;
int n, x, sol = 1;

void init(){
    vi tmp = a;
    reverse(tmp.begin(), tmp.end());
    for (auto& i : tmp)
        i *= -1;

    vi v(n + 1, INT32_MAX);
    v[0] = INT32_MIN;

    for (int i = 0; i < n; ++i){
        int y = tmp[i], ind = lower_bound(v.begin(), v.end(), y) - v.begin();

        v[ind] = y;
        lds[i] = ind;
    }

    reverse(lds.begin(), lds.end());
}

unordered_map<int, int> mapa;
set<int> st;
void kompresuj(){
    mapa.reserve(131072 * 2);
    mapa.max_load_factor(0.25);

    int cur = 0;
    for (auto& i : st){
        mapa[i] = ++cur;
    }

    for (int i = 0; i < n; ++i)
        c[i] = mapa[a[i]];
}

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);

    cin >> n >> x;
    a = vi(n, 0);
    for (auto& i : a){
        cin >> i;
        st.insert(i);
    }

    lds = vi(n, 0);
    init();
    c = vi(n, 0);
    kompresuj();

    vi b(n + 1, INT32_MAX);
    b[0] = INT32_MIN;
    for (int i = 0; i < n; ++i){

        int ind = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
        sol = max(sol, ind);
        b[ind] = a[i];

        int res = lds[i];
        //treba mi lis:. se zavrsava u < a[i] + x
        //odnosno nadjes u st zadnji broj koji je manji od a[i] + x
        //ako ne postoji skip
        //ako postoji nadjes ga u c
        //i vratis get(1, c);

        auto it = st.lower_bound(a[i] + x);
        if (it == st.begin()){
            drvo.add(c[i], ind);
            continue;
        }
        --it;
        int y = mapa[*it];

        res += drvo.get(1, y).x;
 //       cout << res << endl;
        sol = max(sol, res);
        drvo.add(c[i], ind);
    }

   // for (auto& i : lds)
     //   cout << i << ' ';

    cout << sol << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25