题解归档 - cf2230E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2230E
• 本地来源：problems/cf2230E/idea.md
• 题目链接：https://codeforces.com/contest/2230/problem/E
• 原始标题：cf2230E

思路

cf2230E

pattern: monotone domination plus Pareto frontier range queries.

claim: Any news point dominated by another point with both p and c no larger can be deleted. On the remaining frontier sorted by p, c is strictly decreasing. For one query, the three p-zones and three c-zones split this frontier into contiguous intervals, so the nine influence cases reduce to interval existence, endpoint minima, and range minimum of p+c.

necessary: The influence contribution is nondecreasing in p and in c, so a dominated point can never give a smaller value. On the frontier, p increasing forces c decreasing, which makes threshold cuts contiguous.

sufficient: Every point belongs to exactly one of the 3 by 3 zones: below tolerance, inside the influence zone, or capped. The corresponding cost is one of 0, p, c, p+c, X, Y, p+Y, X+c, X+Y, where X=tp+d and Y=tc+d. Taking the minimum over the corresponding frontier interval covers all points.

brute/check: For small random instances, compare the frontier interval algorithm against direct O(nm) evaluation over all news points, including d=0.

edge: d=0 makes the middle zones empty. Thresholds can exceed all coordinates.

代码

来源：problems/cf2230E/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=400005;
const ll inf=4000000000000000000LL;
pair<ll,ll>q[maxn+5];
ll p[maxn+5],c[maxn+5],tp[maxn+5],tc[maxn+5],d[maxn+5],tree[maxn*4+5],cnt,ans;
void build(ll rt,ll l,ll r){
    ll mid;
    if(l==r){
        tree[rt]=p[l]+c[l];
        return;
    }
    mid=(l+r)/2;
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    tree[rt]=min(tree[rt*2],tree[rt*2+1]);
}
ll query(ll rt,ll l,ll r,ll L,ll R){
    ll mid,res;
    if(L<=l and r<=R) return tree[rt];
    mid=(l+r)/2;
    res=inf;
    if(L<=mid) res=min(res,query(rt*2,l,mid,L,R));
    if(R>mid) res=min(res,query(rt*2+1,mid+1,r,L,R));
    return res;
}
ll findc(ll x){
    ll l,r,mid,res;
    l=1;
    r=cnt;
    res=cnt+1;
    while(l<=r){
        mid=(l+r)/2;
        if(c[mid]<x){
            res=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return res;
}
void upd(ll l,ll r,ll v){
    if(l<=r and v<ans) ans=v;
}
int main(){
    ll n,m,i,A,B,D,X,Y,pa,px,cy,cb,l,r,best;
    scanf("%lld",&n);
    for(i=1;i<=n;i++) scanf("%lld",&q[i].first);
    for(i=1;i<=n;i++) scanf("%lld",&q[i].second);
    sort(q+1,q+n+1);
    cnt=0;
    best=inf;
    for(i=1;i<=n;i++){
        if(q[i].second<best){
            cnt++;
            p[cnt]=q[i].first;
            c[cnt]=q[i].second;
            best=q[i].second;
        }
    }
    build(1,1,cnt);
    scanf("%lld",&m);
    for(i=1;i<=m;i++) scanf("%lld",&tp[i]);
    for(i=1;i<=m;i++) scanf("%lld",&tc[i]);
    for(i=1;i<=m;i++) scanf("%lld",&d[i]);
    for(i=1;i<=m;i++){
        A=tp[i];
        B=tc[i];
        D=d[i];
        X=A+D;
        Y=B+D;
        pa=lower_bound(p+1,p+cnt+1,A)-p;
        px=lower_bound(p+1,p+cnt+1,X)-p;
        cy=findc(Y);
        cb=findc(B);
        ans=inf;
        l=max(1LL,cb);
        r=pa-1;
        upd(l,r,0);
        l=max(1LL,cy);
        r=min(pa-1,cb-1);
        if(l<=r) upd(l,r,c[r]);
        l=1;
        r=min(pa-1,cy-1);
        upd(l,r,Y);
        l=max(pa,cb);
        r=px-1;
        if(l<=r) upd(l,r,p[l]);
        l=max(px,cb);
        r=cnt;
        upd(l,r,X);
        l=max(pa,cy);
        r=min(px-1,cb-1);
        if(l<=r) upd(l,r,query(1,1,cnt,l,r));
        l=pa;
        r=min(px-1,cy-1);
        if(l<=r) upd(l,r,p[l]+Y);
        l=max(px,cy);
        r=min(cnt,cb-1);
        if(l<=r) upd(l,r,X+c[r]);
        l=px;
        r=min(cnt,cy-1);
        upd(l,r,X+Y);
        printf("%lld\n",ans);
    }
    return 0;
}