razgovori.cpp

Bài toán

Độ phức tạp

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

using namespace std;

#define long long long

typedef pair<long, long> ii;

#define X first

#define Y second

int n;

long a[102309];

ii b[102309];

int M[21][302309];

int bolji(int p, int q){

    if (p==0 || q==0) return p+q;

    return a[p]<a[q] ? p : q;

}

void rmq(){

    int i, k, delta;

    for (i=1; i<=n; i++) M[0][i]=i;

    for (k=1; delta=(1<<k), delta<=n; k++)

    for (i=1; i<=n; i++)

    M[k][i] = bolji(M[k-1][i], M[k-1][i+delta/2]);

}

int rmq(int ll, int rr){

    int k=0; while ((1<<k+1) <= (rr-ll+1)) k++;

    int delta = (1<<k);

    return bolji(M[k][ll], M[k][rr-delta+1]);

}

int rmq_2(int ll, int rr){

    int r = ll;

    for (int i=ll; i<=rr; i++)

    r = bolji(i, r);

    return r;

}

long f(int ll, int rr, int used){

    int k = rmq(ll, rr);

    long r=0;

    if (k!=ll) r += f(ll, k-1, a[k]);

    if (k!=rr) r += f(k+1, rr, a[k]);

    return r + a[k] - used;

}

long f_2(int ll, int rr, int used){

    int k = rmq_2(ll, rr);

    long r=0;

    if (k!=ll) r += f(ll, k-1, a[k]);

    if (k!=rr) r += f(k+1, rr, a[k]);

    return r + a[k] - used;

}

main(){

    int i;

    scanf("%d%*d", &n);

    //srand(10000*n);

    for (i=1; i<=n; i++){

        scanf("%lld%lld", &b[i].X, &b[i].Y);

        //b[i].X = i;

        //b[i].Y = rand()%1000000000;

    }

    sort(b+1, b+n+1);

    for (i=1; i<=n; i++) a[i]=b[i].Y;

    rmq();

    /*for (int k=0; k<=10; k++){

        for (i=1; i<=n; i++)

        printf("%d ", M[k][i]);

        printf("\n");

    }*/

    printf("%lld\n", f(1, n, 0));

    //printf("%lld\n", f_2(1, n, 0));

}

Nhận xét