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