Vrăjitorul Arpsod este deranjat la culme de câinii vecinului. Aceștia au prostul obicei de a veni să-și îngroape oasele în curtea vrăjitorului. Înainte de a lua măsuri drastice împotriva vecinului, Arpsod a decis să construiască un gard despărțitor între cele două curți. Gardul poate fi privit ca un segment de dreaptă de lungime N metri. Astfel, Arpsod a angajat K meseriași pentru a-i construi gardul. Fiind un tărâm cât se poate de democratic, fiecare muncitor a decis că el este dispus să construiască doar o parte din gard pornind de la al x-lea metru și pană la al y-lea metru inclusiv. Fiecare meseriaș cere o anumită sumă de bani pentru lucrarea sa.

Arpsod poate decide să angajeze o parte dintre muncitori, pentru a realiza întregul gard. Dacă doi muncitori angajați au de construit o porțiune comună a gardului, ea va fi lucrată de amândoi, dar fiecare își va primi integral suma solicitată.

Cerința

Ajutați-l pe Arpsod să-și aleagă meseriașii astfel încât gardul să fie construit integral și el să plătească o sumă minimă de bani.

Date de intrare

Pe prima linie a fișierului gard1.in se află două numere naturale separate prin spațiu: N și K, reprezentând lungimea gardului și numărul de meseriași disponibili. Pe următoarele K linii se vor afla trei valori separate prin spațiu x, y, c, corespunzaoare fiecărui meseriaș: acest meseriaș este dispus să construiască gardul pornind de la al x-lea metru pană la al y-lea metru inclusiv, cerând pentru lucrarea sa prețul c.

Date de ieșire

In fișierul gard1.out se va scrie pe prima linie o singură valoare naturală reprezentând costul minim pe care îl poate plăti Arpsod pentru a i se construi integral gardul.

Restricții și precizări

1 ≤ N, K ≤ 100.000
1 ≤ x ≤ y ≤ N
1 ≤ c ≤ 1.000.000
Se garantează că mereu există soluție.
Se garantează că pentru 20% din teste 1 ≤ K ≤ 10 și 1 ≤ c ≤ 3000
Se garantează că pentru alte 30% din teste 1 ≤ N, K ≤ 1000 și 1 ≤ c ≤ 30000

Exemplu

gard1.in

gard1.out

Explicație

Se aleg bucățile

1..7 cu cost 5
5..8 cu cost 1
9..10 cu cost 2

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema gard1:

// implementare: Cristi Dospra
// punctaj: 100p
// complexitate: O( K * log N )

#include <fstream>
#include <algorithm>
using namespace std;

#define NMAX 100002
#define inf 1e12
#define L(x) ((x) << 1)
#define R(x) ((x) << 1) + 1

ifstream fin("gard.in");
ofstream fout("gard.out");

struct Interv {
    int x, y, c;
}v[NMAX];

long long Aint[4 * NMAX], Lazy[4 * NMAX];

bool cmp(Interv A, Interv B) {

    if (A.y == B.y)
        return A.x < B.x;

    return A.y < B.y;
}

void Build(int nod, int st, int dr) {

    if (st == dr) {
        Aint[nod] = Lazy[nod] = inf;
        return;
    }

    int mid = (st + dr) >> 1;

    Build(L(nod), st, mid);
    Build(R(nod), mid+1, dr);

    Aint[nod] = Lazy[nod] = inf;

}

long long Query(int nod, int st, int dr, int a, int b) {

    if (a < 1)
        return 0;

    if (Lazy[nod] != inf) {
        Aint[nod] = min (Aint[nod], Lazy[nod]);

        if (st != dr) {
            Lazy[L(nod)] = min(Lazy[L(nod)], Lazy[nod]);
            Lazy[R(nod)] = min(Lazy[R(nod)], Lazy[nod]);
        }
        Lazy[nod] = inf;
    }

    if (a <= st && dr <= b)
        return Aint[nod];

    int mid = (st + dr) >> 1;
    long long t1 = inf, t2 = inf;

    if (a <= mid)
        t1 = Query(L(nod), st, mid, a, b);
    if (b > mid)
        t2 = Query(R(nod), mid+1, dr, a, b);

    return min ( t1, t2 );

}

void Update(int nod, int st, int dr, int a, int b, long long val) {

    if (Lazy[nod] != inf) {
        Aint[nod] = min(Aint[nod], Lazy[nod]);
        
        if (st != dr) {
            Lazy[L(nod)] = min(Lazy[L(nod)], Lazy[nod]);
            Lazy[R(nod)] = min(Lazy[R(nod)], Lazy[nod]);
        }
        Lazy[nod] = inf;
    }

    if (a <= st && dr <= b) {
        Aint[nod] = min(Aint[nod], val);
        
        if (st != dr) {
            Lazy[L(nod)] = min (Lazy[L(nod)], val);
            Lazy[R(nod)] = min (Lazy[R(nod)], val);
        }
        
        return;
    }

    int mid = (st + dr) >> 1;

    if (a <= mid)
        Update(L(nod), st, mid, a, b, val);
    if (b > mid)
        Update (R(nod), mid+1, dr, a, b, val);

    Aint[nod] = min(Aint[L(nod)], Aint[R(nod)]);
}

int main(){

    int N, K;

    fin >> N >> K;

    Build(1, 1, N);

    for (int i = 1; i <= K; ++i)
        fin >> v[i].x >> v[i].y >> v[i].c;

    sort(v + 1, v + K + 1, cmp);

    long long aux;

    for (int i = 1; i <= K; ++i) {
        int x = v[i].x;
        int y = v[i].y;
        
        aux = Query(1, 1, N, x-1, x-1);
        Update(1, 1, N, x, y, aux + v[i].c);
    }

    fout << Query(1, 1, N, N, N);

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2022 gard1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2022 gard1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2022 gard1