Submission #1235791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235791		kaltspielerhy	Global Warming (CEOI18_glo)	C++20	100 / 100	965 ms	29776 KiB

glo

#include <bits/stdc++.h>
using namespace std;
int MAX_N = (1 << 19);
int MAX_NOEUDS = MAX_N*2;
int INFINI = 1e9;

map<int, int> a;
int cpt = 2;

struct segtree {
    int N;
    vector<vector<int>> arbre;

    segtree(int _N) {
        arbre.resize(2);
        arbre[0].resize(MAX_NOEUDS, -INFINI);
        arbre[1].resize(MAX_NOEUDS, -INFINI);
        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);
        arbre[0][cpt] = 0;
        arbre[1][cpt] = 0;
        modif(cpt, 0, 0);
        modif(cpt, 0, 1);
    }

    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;
    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 dp3 = -INFINI;
        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);
    }

    int maxi1 = max(binary.maxIntervalle(1, 0, MAX_N-1, 0, cpt, 0), binary.maxIntervalle(1, 0, MAX_N-1, 0, cpt, 1));
    reverse(nums.begin(), nums.end());
    binary.clearing();

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

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

    int maxi2 = max(binary.maxIntervalle(1, 0, MAX_N-1, 0, cpt, 0), binary.maxIntervalle(1, 0, MAX_N-1, 0, cpt, 1));

    cout << max(maxi1, maxi2) << '\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