19032022-12-08 17:50:41sztomiMúzeumi őrökcpp17Futási hiba 32/40177ms63096 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf = 1e16;

int n, e, u;
vector<int> ar;
vector<int> kezd;
vector<int> veg;
vector<int> ind;
vector<pair<ll, vector<int>>> dp;
vector<bool> volt;
vector<pair<ll, vector<int>>> fa;
vector<int> legmesszebb;

int bal(int x){
    return 2*x;
}

int jobb(int x){
    return 2*x+1;
}

int szulo(int x){
    return x / 2;
}

struct comp{
    bool operator()(int a, int b){
        if(kezd[a] < kezd[b]) return true;
        if(kezd[a] > kezd[b]) return false;
        return veg[a] > veg[b];
    }
};


void allit(pair<ll, vector<int>> ertek, int ind){
    if(ind == 0) return;

    if(fa[ind].first > ertek.first){
        fa[ind] = ertek;
        allit(ertek, szulo(ind));
    }
}

pair<ll, vector<int>> legjobb(int keres_e, int keres_u, int elso, int utolso, int ind){
    if(ind >= fa.size()) return {inf, vector<int>()};
    if(keres_u < elso) return {inf, vector<int>()};
    if(keres_e > utolso) return {inf, vector<int>()};
    if(elso > utolso) return {inf, vector<int>()};

    if(elso == utolso) return fa[ind];
    if(keres_e <= elso && utolso <= keres_u) return fa[ind];

    pair<ll, vector<int>> id1, id2;
    id1 = legjobb(keres_e, keres_u, elso, (elso + utolso) / 2, bal(ind));
    id2 = legjobb(keres_e, keres_u, (elso + utolso) / 2 + 1, utolso, jobb(ind));
    if(id1.first < id2.first){
        return id1;
    }
    else{
        return id2;
    }
}



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

    cin >> n >> e >> u;
    u -= e-1;
    ar.assign(n+1, 0);
    kezd.assign(n+1, 0);
    veg.assign(n+1, 0);
    ind.assign(n+1, 0);
    dp.resize(n+1);
    volt.assign(n+1, false);

    for(int i = 1; i <= n; i++){
        ind[i] = i;
        cin >> kezd[i] >> veg[i] >> ar[i];
        kezd[i] -= e-1;
        veg[i] -= e-1;
    }
    sort(ind.begin(), ind.end(), comp());

    /*
    cout << "-------------\n";
    for(int x : ind){
        cout << kezd[x] << " " << veg[x] << " " << ar[x] << "\n";
    }
    cout << "---\n";
    */

    // minden allashoz a legmessszebb elerot beallitani
    legmesszebb.assign(n+1, -1);
    for(int i = 0; i <= n; i++){
        int l, r, m;
        l = i;
        r = n;
        while(l <= r){
            m = (l+r) / 2;
            if(veg[ind[i]] + 1 >= kezd[ind[m]]){
                l = m + 1;
                legmesszebb[i] = m;
            }
            else{
                r = m-1;
            }
        }
    }

    // szegmensfa inicializalas
    int fa_meret = 131072;
    fa.assign(2*fa_meret+1, {inf, vector<int>()});

    pair<ll, vector<int>> ret, ideigl;
    for(int utolso = n; utolso >= 0; utolso--){
        if(veg[ind[utolso]] == u){
            ret = {ar[ind[utolso]], vector<int>()};
            ret.second.push_back(ind[utolso]);
        }
        else{
            ret = legjobb(utolso+1, legmesszebb[utolso], 0, fa_meret-1, 1);
            if(ret.first != inf){
                ret.first += ar[ind[utolso]];
                ret.second.push_back(ind[utolso]);
            }
        }
        allit(ret, utolso + fa_meret);
/*
        for(int i = fa_meret; i <= fa_meret + n; i++){
            cout << fa[i].first << " ";
        }
        cout << "\n";
*/
        dp[utolso] = ret;
    }
    ret = dp[0];


    if(ret.first == inf){
        cout << "-1\n";
    }
    else{
        cout << ret.first << "\n";
        cout << ret.second.size()-1 << " ";
        for(int i = ret.second.size()-2; i >= 0; i--){
            cout << ret.second[i] << " ";
        }
        cout << "\n";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base32/40
1Elfogadva0/09ms17972 KiB
2Futási hiba0/041ms61840 KiB
3Elfogadva1/19ms18600 KiB
4Elfogadva3/38ms18708 KiB
5Elfogadva2/28ms18916 KiB
6Elfogadva2/28ms19116 KiB
7Elfogadva2/28ms19212 KiB
8Elfogadva2/28ms19260 KiB
9Elfogadva2/29ms19308 KiB
10Futási hiba0/2177ms62844 KiB
11Futási hiba0/2171ms63096 KiB
12Elfogadva2/28ms19984 KiB
13Elfogadva2/217ms22524 KiB
14Elfogadva3/339ms48492 KiB
15Elfogadva3/343ms52504 KiB
16Futási hiba0/2173ms63024 KiB
17Futási hiba0/2172ms62788 KiB
18Elfogadva2/29ms20320 KiB
19Elfogadva2/28ms20464 KiB
20Elfogadva2/28ms20432 KiB
21Elfogadva2/28ms20432 KiB