Submission #1216298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216298		kaltspielerhy	Grudanje (COCI19_grudanje)	C++20	70 / 70	1757 ms	87816 KiB

grudanje

#include <bits/stdc++.h>
using namespace std;
const int INFINI = 1e9;

struct node {
    int vMax = -1e9;      // max sur l'intervalle
    int vSecondMax = -1e9; // 2e max sur l'intervalle
};

struct segTree {
    int N;
    vector<node> arbre;

    segTree(int _N) {
        N = _N;
        arbre.resize(4*N);
    }

    node merge(const node& a, const node& b) {
        vector<int> vals = {a.vMax, a.vSecondMax, b.vMax, b.vSecondMax};
        sort(vals.begin(), vals.end(), greater<int>());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());

        node res;
        res.vMax = vals[0];
        res.vSecondMax = (int)vals.size() > 1 ? vals[1] : -1e9;
        return res;
    }

    void build(const vector<int>& arr, int noeud = 1, int debut = 0, int fin = -1) {
        if (fin == -1) fin = N-1;
        if (debut == fin) {
            arbre[noeud].vMax = arr[debut];
            arbre[noeud].vSecondMax = -1e9;
            return;
        }
        int mid = (debut + fin) / 2;
        build(arr, noeud*2, debut, mid);
        build(arr, noeud*2+1, mid+1, fin);
        arbre[noeud] = merge(arbre[noeud*2], arbre[noeud*2+1]);
    }

    void update(int idx, int val, int noeud = 1, int debut = 0, int fin = -1) {
        if (fin == -1) fin = N-1;
        if (debut == fin) {
            arbre[noeud].vMax = val;
            arbre[noeud].vSecondMax = -1e9;
            return;
        }
        int mid = (debut + fin) / 2;
        if (idx <= mid) update(idx, val, noeud*2, debut, mid);
        else update(idx, val, noeud*2+1, mid+1, fin);
        arbre[noeud] = merge(arbre[noeud*2], arbre[noeud*2+1]);
    }

    node query(int l, int r, int noeud = 1, int debut = 0, int fin = -1) {
        if (fin == -1) fin = N-1;
        if (r < debut || l > fin) return {-INFINI, -INFINI};
        if (l <= debut && fin <= r) return arbre[noeud];
        int mid = (debut + fin) / 2;
        node gauche = query(l, r, noeud*2, debut, mid);
        node droite = query(l, r, noeud*2+1, mid+1, fin);
        return merge(gauche, droite);
    }
};

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

    string mot;
    getline(cin, mot);
    int N = mot.size();
    vector<vector<int>> lettres(26);
    for (int i = 1; i <= N; i++) {
        lettres[mot[i-1] - 'a'].push_back(i);
    }
    int nbIntervalles;
    cin >> nbIntervalles;
    vector<pair<int, int>> intervalles(nbIntervalles);
    for (auto& iInter : intervalles) cin >> iInter.first >> iInter.second;
    vector<int> ordre(N);
    vector<int> ordreInverse(N);
    vector<vector<int>> temps(26);
    for (int& iOrd : ordre) cin >> iOrd;
    int compteur = 1;
    for (int i : ordre){ ordreInverse[i-1] = compteur; compteur++;}
    for (int iLettre = 0; iLettre < 26; iLettre++) {
        for (int iValeur : lettres[iLettre])
            temps[iLettre].push_back(ordreInverse[iValeur-1]);
    }

    // for (int i = 0; i < 26; i++) {
    //     for (auto obj : temps[i]) cout << obj << ' ';
    //     cout << '\n';
    // }

    vector<segTree> arbres;
    for (int i = 0; i < 26; i++) arbres.push_back(segTree(N));

    for (int iLettre = 0; iLettre < 26; iLettre++) {
        if (!temps[iLettre].empty()) {
            arbres[iLettre] = segTree((int)temps[iLettre].size());
            arbres[iLettre].build(temps[iLettre]);
        }
    }

    int result = 0;
    for (auto [debut, fin] : intervalles) {
        int act = 0;
        for (int iLettre = 0; iLettre < 26; iLettre++) {
            int positionDep = lower_bound(lettres[iLettre].begin(), lettres[iLettre].end(), debut) - lettres[iLettre].begin();
            int positionFin = upper_bound(lettres[iLettre].begin(), lettres[iLettre].end(), fin) - lettres[iLettre].begin();
            if (positionFin - positionDep >= 2) {
                node res = arbres[iLettre].query(positionDep, positionFin - 1);
                act = max(act, res.vSecondMax);
            }
        }
        result = max(result, act);
    }

    cout << result << '\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7