QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#586744	#7944. Max Minus Min	Math4Life2020	TL	970ms	17960kb	C++20	4.4kb	2024-09-24 15:19:14	2024-09-24 15:19:15

Judging History

你现在查看的是最新测评结果

[2024-09-24 15:19:15]
评测

测评结果：TL
用时：970ms
内存：17960kb

查看

[2024-09-24 15:19:14]
提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = INT_MAX;

vector<ll> stmax,stmin;
ll E; ll Nm;

ll e2(ll x) {
    return (1LL<<x);
}

ll l2(ll x) {
    return (31-__builtin_clz(x));
}

ll v2(ll x) {
    if (x==0) {
        return 100;
    }
    return __builtin_ctz(x);
}

ll qmax(ll a, ll b) {
    if (a>b) {
        return -INF;
    }
    ll va = v2(a); ll vb = v2(b+1);
    if (va>vb) {
        return max(qmax(a,b-e2(vb)),stmax[(b>>vb)+e2(E-vb)]);
    } else {
        return max(qmax(a+e2(va),b),stmax[(a>>va)+e2(E-va)]);
    }
}

ll qmin(ll a, ll b) {
    if (a>b) {
        return INF;
    }
    ll va = v2(a); ll vb = v2(b+1);
    if (va>vb) {
        return min(qmin(a,b-e2(vb)),stmin[(b>>vb)+e2(E-vb)]);
    } else {
        return min(qmin(a+e2(va),b),stmin[(a>>va)+e2(E-va)]);
    }
}

ll solve(ll N, vector<ll> inpV) {
    //freopen("input.txt","r",stdin);
    stmax.clear();
    stmin.clear();
    if (N==1) {
        return 0;
    }
    E = l2(N-1)+1;
    Nm = e2(E);
    //cout << "E,Nm="<<E<<","<<Nm<<"\n";
    for (ll i=0;i<(2*Nm);i++) {
        stmax.push_back(0);
        stmin.push_back(0);
    }
    for (ll i=0;i<N;i++) {
        stmax[i+Nm]=inpV[i];
        stmin[i+Nm]=stmax[i+Nm];
    }
    for (ll d=(Nm-1);d>=1;d--) {
        stmax[d]=max(stmax[2*d],stmax[2*d+1]);
        stmin[d]=min(stmin[2*d],stmin[2*d+1]);
    }
    ll ans = stmax[1]-stmin[1];
    for (ll x=0;x<N;x++) {
        ll ymin=x; ll ymax=N-1;
        while (ymin!=ymax) {
            ll yt = (ymin+ymax+1)/2;
            ll d1 = max(qmax(0,x-1),qmax(yt+1,N-1))-min(qmin(0,x-1),qmin(yt+1,N-1));
            if (d1<0) {
                ymax=yt-1; continue;
            }
            ll d2 = qmax(x,yt)-qmin(x,yt);
            //cout << "x,yt,d1,d2="<<x<<","<<yt<<","<<d1<<","<<d2<<"\n";
            ans = min(ans,max(d1,d2));
            if (d1<d2) {
                ymax=yt-1;
            } else {
                ymin=yt;
            }
        }
       /* while (1) {
            ll yt = ymin-1;
            if (yt<x) {
                break;
            }
            ll d1 = max(qmax(0,x-1),qmax(yt+1,N-1))-min(qmin(0,x-1),qmin(yt+1,N-1));
            if (d1<0) {
                break;
            }
            ll d2 = qmax(x,yt)-qmin(x,yt);
            ans = min(ans,max(d1,d2));
            break;
        }*/
        while (1) {
            ll yt = ymin;
            if (yt<x) {
                break;
            }
            ll d1 = max(qmax(0,x-1),qmax(yt+1,N-1))-min(qmin(0,x-1),qmin(yt+1,N-1));
            if (d1<0) {
                break;
            }
            ll d2 = qmax(x,yt)-qmin(x,yt);
            ans = min(ans,max(d1,d2));
            break;
        }
    }
    return ans;
}

ll solvebash(ll N, vector<ll> a) {
    ll ans = INF;
    for (ll i=0;i<N;i++) {
        for (ll j=0;j<N;j++) {
            if (i==0 && j==(N-1)) {
                continue;
            }
            ll uo=-INF; ll ui=-INF; ll lo=INF; ll li=INF;
            for (ll x=i;x<=j;x++) {
                ui=max(ui,a[x]);
                li=min(li,a[x]);
            }
            for (ll x=0;x<i;x++) {
                uo=max(uo,a[x]);
                lo=min(lo,a[x]);
            }
            for (ll x=(j+1);x<N;x++) {
                uo=max(uo,a[x]);
                lo=min(lo,a[x]);
            }
            //cout << "uo,ui,lo,li="<<uo<<","<<ui<<","<<lo<<","<<li<<"\n";
            if (ui<li) {
                continue;
            }
            if (uo<lo) {
                continue;
            }
            ans = min(ans,max(uo-lo,ui-li));
        }
    }
    return ans;
}

void input() {
    ll N; cin >> N;
    vector<ll> inpV;
    for (ll i=0;i<N;i++) {
        ll x; cin >> x;
        inpV.push_back(x);
    }
    cout << solve(N,inpV) <<"\n";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll T; cin >> T;
    while (T--) {
        input();
    }
}

/*int main() {
    mt19937 gen((long long) new char);
    for (ll T=0;T<100;T++) {
        ll N=6;
        vector<ll> vn;
        for (ll i=0;i<N;i++) {
            vn.push_back(gen()%10);
        }
        if (solve(N,vn)!=solvebash(N,vn)) {
            for (ll x: vn) {
                cout << x <<"\n";
            }
            exit(0);
        }
    }
    cout << "done!\n";
}*/

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3836kb

input:

4
3
42 42 42
4
1 2 2 1
5
1 100 1 100 1
6
1 2 3 4 5 6

output:

result:

ok 4 number(s): "0 0 99 2"

Test #2:

score: 0

Accepted

time: 16ms

memory: 3556kb

input:

19530
6
2 3 3 3 4 3
6
2 4 4 2 5 5
6
2 5 2 5 1 3
6
4 4 1 2 4 1
5
5 4 5 3 3
5
2 2 1 5 1
6
3 1 2 4 2 3
5
5 5 4 4 5
6
5 3 3 1 4 2
6
3 3 2 4 2 4
6
1 2 4 5 2 5
5
3 4 5 5 3
6
4 3 3 3 4 3
6
1 5 1 2 3 1
5
5 5 2 1 4
6
1 2 5 3 5 2
6
4 5 2 4 5 2
5
2 4 2 4 1
4
2 3 3 3
6
1 2 2 1 4 5
6
3 2 1 3 3 2
6
2 1 1 2 5 3
6
...

output:

result:

ok 19530 numbers

Test #3:

score: 0

Accepted

time: 970ms

memory: 17960kb

input:

1
199996
95228303 201285494 63848235 748936712 940169142 379639162 189291770 224201078 335564466 792345215 948056869 35198826 312793561 194588099 297198853 665606109 163797196 584404459 996890415 458867609 331820116 713293915 858136035 520976262 519894660 918315819 660535535 639896052 141007070 1151...

output:

999986012

result:

ok 1 number(s): "999986012"

Test #4:

score: -100

Time Limit Exceeded

input:

1
199998
527515482 831759304 786398217 142876272 541300660 926936654 117644051 72438862 579434512 298922247 726038416 333034763 721144032 811978092 585764800 216757507 702854739 157207076 124829370 951519274 884953479 246664247 437913730 867100723 186107370 511591980 673723365 46011051 452152759 270...