Submission #607646

#	Time	Username	Problem	Language	Result	Execution time	Memory
607646		AlbertoTDNeto	Global Warming (CEOI18_glo)	C++17	100 / 100	1008 ms	76540 KiB

glo

#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define sws ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define teto(a, b) ((a+b-1)/(b))r
using namespace std;

// Extra
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//

const int MAX = 300010;
const ll MOD = (int)1e9 +7;
const int INF = 1e9;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ld EPS = 1e-8;

// colocar suposicoes no PAPEL!! Verificar depois

struct ST {
    vector<ll> v;
    int size;

    ST(int n) {
        size = 1;
        while(size < n) size *= 2;
        v.assign(2*size, 0);
    }

    ll f(ll a, ll b) {
        return max(a, b);
    }

    ll query(int l, int r, int x, int lx, int rx) {
        if(rx <= l or r <= lx) return 0;
        if(l <= lx and rx <= r) return v[x];

        int mid = (lx + rx)/2;

        auto s1 = query(l, r, 2*x+1, lx, mid);
        auto s2 = query(l, r, 2*x+2, mid, rx);

        return f(s1, s2);
    }

    void update(int i, int val, int x, int lx, int rx) {
        if(rx - lx == 1) {
            v[x] = val;
            return;
        }

        int mid = (lx + rx)/2;
        if(lx <= i and i < mid) {
            update(i, val, 2*x+1, lx, mid);
        }
        else {
            update(i, val, 2*x+2, mid, rx);
        }

        v[x] = f(v[2*x+1], v[2*x+2]);
    }

    ll query(int l, int r) {
        return query(l, r+1, 0, 0, size);
    }

    void update(int i, int val) {
        update(i, val, 0, 0, size);
    }
};

map<int,int> comp;

int32_t main() {
    int n, x;
    cin >> n >> x;

    // leitura
    vector<int> c; c.reserve(4*n);
    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];

        c.pb(v[i]);
        c.pb(v[i]-1);
        c.pb(v[i]+x);
        c.pb(v[i]+x-1);
    }

    // compressao
    sort(all(c));
    c.erase(unique(all(c)), c.end());

    for(int i = 0; i < (int)c.size(); i++) {
        comp[c[i]] = i+1;
    }

    ST st(5*n+5), stsoma(5*n+5);

    // for(int i = 0; i < n; i++) {
    //     cout << comp[v[i]] << " ";
    // }
    // cout << endl;
    //
    // cout << comp[2] << endl;

    // LIS
    for(int i = 0; i < n; i++) {
        // pega sem somar
        int qt = st.query(0, comp[v[i]-1])+1;

        // pega somando
        int qtsoma = max( st.query(0, comp[v[i]+x-1]) , stsoma.query(0, comp[v[i]+x-1]) ) + 1;

        // cout << "i = " << i << " qt = " << qt << " qtsoma = " << qtsoma << " aa = " << comp[v[i]-1] << " " << comp[v[i]] << endl;

        // atualiza depois das queries hehe
        st.update(comp[v[i]], qt);
        stsoma.update(comp[v[i]+x], qtsoma);
    }

    // cout << max( st.query(0, c.size()-1), stsoma.query(0, c.size()-1) ) << endl;
    cout << stsoma.query(0, 4*n+4) << endl;

    return 0;
}

• 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