QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#586760	#7944. Max Minus Min	Math4Life2020	TL	935ms	8992kb	C++20	4.4kb	2024-09-24 15:23:47	2024-09-24 15:23:50

Judging History

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

[2024-09-24 15:23:50]
评测

测评结果：TL
用时：935ms
内存：8992kb

查看

[2024-09-24 15:23:47]
提交

answer

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
const ll INF = INT_MAX;

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

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

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

ll v2(ll x) {
    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";
}*/

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3552kb

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: 15ms

memory: 3592kb

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: 935ms

memory: 8992kb

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...

output:

999982414