Submission #1235772

#TimeUsernameProblemLanguageResultExecution timeMemory
1235772kaltspielerhyGlobal Warming (CEOI18_glo)C++20
10 / 100
248 ms25692 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = (1 << 18);
const int MAX_NOEUDS = MAX_N*2;
const int INFINI = 1e9;

map<int, int> a;

struct segtree {
    int N;
    int arbre[2][MAX_NOEUDS];

    segtree(int _N) {
        fill(arbre[0], arbre[0]+MAX_NOEUDS, -1);
        fill(arbre[1], arbre[1]+MAX_NOEUDS, -1);
        arbre[0][0] = 0;
        arbre[1][0] = 0;
        modif(0, 0, 0);
        modif(0, 0, 1);
    }

    // void clearing() {
    //     arbre[0].assign(MAX_NOEUDS, -INFINI);
    //     arbre[1].assign(MAX_NOEUDS, -INFINI);
    // }

    void modif(int noeud, int elem, int num) {
        noeud += MAX_N;
        arbre[num][noeud] = max(arbre[num][noeud], elem);
        while (noeud != 1) {
            noeud /= 2;
            arbre[num][noeud] = max(arbre[num][noeud*2], arbre[num][noeud*2+1]);
        }
    }

    int maxIntervalle(int node, int dI, int fI, int dR, int fR, int num) {
        if (dI > fR || dR > fI) return -1;
        if (dR <= dI && fR >= fI) return arbre[num][node];

        int mid = (dI+fI)/2;
        int gauche = maxIntervalle(node*2, dI, mid, dR, fR, num);
        int droite = maxIntervalle(node*2+1, mid+1, fI, dR, fR, num);
        return max(gauche, droite);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, x;
    cin >> N >> x;
    vector<int> nums(N);
    for (int& i : nums)cin >> i;

    vector<int> numsSorted = nums;
    for (int i = 0; i < N; i++) numsSorted.push_back(nums[i]+x);
    sort(numsSorted.begin(), numsSorted.end());
    a[numsSorted[0]] = 1;
    int cpt = 2;
    for (int i = 1; i < 2*N; i++) {
        if (numsSorted[i] != numsSorted[i-1]) {
            a[numsSorted[i]] = cpt;
            cpt++;
        }
    }

    segtree binary(N);

    for (int iElem : nums) {
        int num = a[iElem], numx = a[iElem+x];
        int dp1 = binary.maxIntervalle(1, 0, MAX_N-1, 0, num-1, 0);
        int dp2 = binary.maxIntervalle(1, 0, MAX_N-1, 0, num-1, 1);
        int dp3 = binary.maxIntervalle(1, 0, MAX_N-1, 0, numx-1, 0);
        int dp4 = binary.maxIntervalle(1, 0, MAX_N-1, 0, numx-1, 1);

        binary.modif(num, max(dp1, dp2)+1, 0);
        binary.modif(numx, max(dp3, dp4)+1, 1);
    }

    cout << max(binary.maxIntervalle(1, 0, MAX_N-1, 0, cpt, 0), binary.maxIntervalle(1, 0, MAX_N-1, 0, cpt, 1)) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...