QOJ.ac

QOJ

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

Judging History

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

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

测评结果：TL
用时：18ms
内存：3828kb

查看

[2024-09-24 15:13:15]
提交

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";
}*/

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3788kb

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

memory: 3828kb

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: -100

Time Limit Exceeded

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