WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
Codeforces GYM 102001H. Lexical Sign Sequence
Codeforces GYM 102001H. Lexical Sign Sequence

Source: Codeforces 2018 ICPC Asia Jakarta Regional Contest

题目大意

有一个长度为n的只包含{+1, -1}的序列,有些位置已经确定值了而另一些位置没有确定,给你K 个条件要求,区间[L_i, R_i]之和要大于等于P_i,让你构造一个字典序最小的可行答案序列。

题解

因为要构造字典序最小,所以很容易想到从头到尾按位确定答案的做法。
我们一开始给所有不确定位置都填上1,判断一下是否可行,如果不可行那么一定没有解。
接下来,只需要从头开始枚举每一个不确定的位,试试看能不能把它从1改成-1,如果改完还满足所有条件那就修改它。然后我们可以知道,当我们修改第i位的时候,我们需要关注的条件是哪些限制区间包含当前位置的条件,将第i位从1改成-1就相当于将这些条件的限制区间中元素之和-2。如果这些条件的限制区间内元素和的最小值大于等于2的话,显然就是可以修改的。
我们将所有限制区间按左端点排序,用扫描线的思路动态加入包含当前考虑位置的条件,同时再对已经加入考虑的条件按照右端点维护一个优先队列,用于删除已经没有用处的条件。因为-2是全局减法,我们可以对减法记录一个Tag,将对条件区间和的减法操作变为对Tag的加法操作,每次比较Tag与当前条件的约束值P_i的大小就可以了。

#include <cstdio>
#include <set>
#include <algorithm>
#include <queue>
#define PII pair<int, int>
using namespace std;

const int MAXN=1e5+50;

int n, K;
int seq[MAXN], ans[MAXN];
struct Constraints{
    int l, r, c;
    int value;
}con[MAXN];

inline bool cmp(const Constraints &a, const Constraints &b){ return a.l<b.l; }

int sum[MAXN+5];
multiset<int> pool;
priority_queue<PII> que;
int main(){
    scanf("%d%d", &n, &K);
    for (int i=1; i<=n; i++) scanf("%d", &seq[i]);
    for (int i=1; i<=K; i++) scanf("%d%d%d", &con[i].l, &con[i].r, &con[i].c);
    sort(con+1, con+K+1, cmp);

    for (int i=1; i<=n; i++) if (seq[i]!=0) ans[i]=seq[i]; else ans[i]=1;
    sum[0]=0; for (int i=1; i<=n; i++) sum[i]=sum[i-1]+ans[i];

    bool flag=true;
    for (int i=1; i<=K && flag; i++){
        con[i].value=sum[con[i].r]-sum[con[i].l-1];
        if (con[i].value<con[i].c) flag=false;
    }
    if (!flag) return printf("Impossible\n")*0;

    int cnt=0;
    for (int i=1, l=0, rate=0; i<=n; i++){
        //printf("Pos %d\n", i);
        if (seq[i]!=0) continue;
        while(l+1<=K && con[l+1].l<=i){
            ++l; ++cnt;
            con[l].value=con[l].value-con[l].c+rate;
            //printf("Add %d %d %d\n", con[l].l, con[l].r, con[l].c);
            pool.insert(con[l].value);
            que.push({-con[l].r, l});
        }
        while(!que.empty() && -que.top().first<i){
            int p=que.top().second; que.pop();
            multiset<int>::iterator it=pool.find(con[p].value);
            pool.erase(it);
            --cnt;
        }

        if (cnt==0) ans[i]=-1, rate+=2; else{
            int mi=*pool.begin();
            //printf("Pos = %d , Mi = %d\n", i, mi);
            if (rate+2<=mi) ans[i]=-1, rate+=2;
        }
    }

    for (int i=1; i<=n; i++) printf("%d ", ans[i]); printf("\n");
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

Codeforces GYM 102001H. Lexical Sign Sequence
Source: Codeforces 2018 ICPC Asia Jakarta Regional Contest 题目大意 有一个长度为$n$的只包含${+1, -1}$的序列,有些位置已经确定值了而另一些位置没有确定,给你$K$ 个…
扫描二维码继续阅读
2018-11-27
<--! http2https -->