题解：P14785 [NERC 2025] Doorway

MaxBlazeResFire · 2025-12-17 22:24:13 · 题解

显然门板要靠边。

那么每一层有 k_i+1 种决策，第 j 种决策可以用 (L_{i,j},R_{i,j}) 来表示，也即这一层的缝隙。

现在需要在每一层选一个决策，最大化 \displaystyle\min R-\max L。

注意到不同的 L 只有 O(\sum k) 个，因此考虑离散化后直接枚举。枚举一个 L 时，显然一层的决策是选择最大的 L_{j}\leq L；又因为同一层所有决策中 L 单调增加，R 单调递减，所以每个 R 对一个枚举时序的后缀生效起取 \min 的作用，我们直接维护每个 R 做出贡献的时刻即可，这是持久化的。

复杂度 O(\sum k\log\sum k)。

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 400005
int n,k[MAXN],X1[MAXN],X2[MAXN];
int ssf[MAXN],cnt = 0;

vector<int> tim[MAXN];
vector< pair<int,int> > T[MAXN];

signed main(){
    scanf("%lld",&n);
    for( int i = 1 ; i <= n ; i ++ ){
        scanf("%lld%lld%lld",&k[i],&X1[i],&X2[i]);
        vector<int> C( k[i] + 1 ),pre( k[i] + 1 ),suf( k[i] + 1 );
        int s = 0;
        for( int j = 1 ; j <= k[i] ; j ++ )
            scanf("%lld",&C[j]),s += C[j];
        pre[0] = X1[i];
        for( int j = 1 ; j <= k[i] ; j ++ )
            pre[j] = pre[j - 1] + C[j];
        suf[0] = X2[i] - s;
        for( int j = 1 ; j <= k[i] ; j ++ )
            suf[j] = suf[j - 1] + C[j];
        for( int j = 0 ; j <= k[i] ; j ++ )
            T[i].emplace_back( make_pair( pre[j] , suf[j] ) );
    }
    for( int i = 1 ; i <= n ; i ++ )
        for( pair<int,int> p : T[i] )
            ssf[++cnt] = p.first;
    sort( ssf + 1 , ssf + cnt + 1 );
    cnt = unique( ssf + 1 , ssf + cnt + 1 ) - ( ssf + 1 );
    for( int i = 1 ; i <= n ; i ++ ){
        for( int j = 0 ; j < k[i] ; j ++ ){
            int id = lower_bound( ssf + 1 , ssf + cnt + 1 , T[i][j + 1].first ) - ssf;
            tim[id - 1].emplace_back( T[i][j].second );
        }
        int id = lower_bound( ssf + 1 , ssf + cnt + 1 , T[i][0].first ) - ssf;
        tim[id - 1].emplace_back( -(int)1e18 ); 
    }
    int Rig = (int)1e18,ans = 0;
    for( int i = 1 ; i <= n ; i ++ ) Rig = min( Rig , T[i][k[i]].second );
    ans = max( ans , Rig - ssf[cnt] );
    for( int Timer = cnt - 1 ; Timer >= 1 ; Timer -- ){
        for( int p : tim[Timer] ) Rig = min( Rig , p );
        ans = max( ans , Rig - ssf[Timer] );
    }
    printf("%lld\n",ans);
    return 0;
}