专栏文章

题解：CF887D Ratings and Reality Shows

__2eyks
CF887D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min6m4a2
此快照首次捕获于
2025/12/01 21:25
3 个月前
此快照最后确认于
2025/12/01 21:25
3 个月前
查看原文
duel 打到的，简单。
考虑枚举脱口秀时间 TT。显然 TT 只有 Θ(n)\Theta(n) 中可能，所以枚举第一个被脱口秀影响到的拍照或时装表演事件。
那可以把问题拆成两个部分，时间 <T<T 和时间 ∈[T,T+len)\in[T,T+len) 时分别满足条件。
对于时间 <T<T 的部分，我们枚举的就是拍照或时装表演事件，所以记录前缀和就可以了。
对于时间 ∈[T,T+len)\in[T,T+len) 的部分，不好直接维护，需要上数据结构。线段树节点维护区间内事件对评分的总贡献，以及这个贡献的前缀 min⁡\min，信息是很好合并的。
需要把 [T,T+len)[T,T+len) 这个区间离散化，然后做完了。
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
const int N=3e5+5;
int n,a,b,c,d,start,len,times[N],op[N];
namespace sgm{
    #define lc (x<<1)
    #define rc (x<<1|1)
    #define mid ((l+r)>>1)
    struct node{
        int delta,mndelta;
        friend node operator+(node x,node y){
            node rs;
            rs.delta=x.delta+y.delta;
            rs.mndelta=min(x.mndelta,x.delta+y.mndelta);
            return rs;
        }
    }dt[N<<2];
    void build(int x,int l,int r){
        if (l==r){
            if (op[l])
                dt[x]={c,c};
            else dt[x]={-d,-d};
            return;
        }
        build(lc,l,mid);
        build(rc,mid+1,r);
        dt[x]=dt[lc]+dt[rc];
    }
    node query(int x,int l,int r,int ql,int qr){
        if (ql<=l&&r<=qr)
            return dt[x];
        if (ql<=mid&&qr>mid)
            return query(lc,l,mid,ql,qr)+query(rc,mid+1,r,ql,qr);
        else if (ql<=mid)
            return query(lc,l,mid,ql,qr);
        else return query(rc,mid+1,r,ql,qr);
    }
}
using namespace sgm;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>a>>b>>c>>d>>start>>len;
    fo(i,1,n)
        cin>>times[i]>>op[i];
    build(1,1,n);
    times[0]=-1;
    fo(i,1,n){
        int L=times[i-1]+1,R=L+len-1;
        int l=lower_bound(times+1,times+n+1,L)-times;
        int r=upper_bound(times+1,times+n+1,R)-times-1;//这里可以双指针，但我是打 duel，懒得写
        if (start+query(1,1,n,l,r).mndelta>=0){
            cout<<L<<'\n';
            return 0;
        }
        if (op[i])
            start+=a;
        else start-=b;
        if (start<0){
            cout<<"-1\n";
            return 0;
        }
    }
    cout<<times[n]+1<<'\n';
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...