首页 > 其他分享 >Codeforces Round #631 (Div. 1) - Thanks, Denis aramis Shitov! A

Codeforces Round #631 (Div. 1) - Thanks, Denis aramis Shitov! A

时间:2022-10-28 10:45:32浏览次数:76  
标签:631 const 10 int Codeforces aramis 板子 mx

A. Dreamoon Likes Coloring

显然我们不看把整块涂满 最优的构造
就是1 2 3 4....
但是要考虑将整块板涂满
我们就要往右挪 显然我们每次挪后面的板子都会动
我们一定要让后面的板子都不能超过总长
我们用st表维护后面的板子最右端的最长即可

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int f[N][30],n,b[N],m;
void init(){
    for(int len=0;len<30;len++){
        for(int i=1;i+(1<<len)-1<=m;i++){
            if(!len)f[i][len]=b[i];
            else f[i][len]=max(f[i][len-1],f[i+(1<<(len-1))][len-1]);
        }   //i+1<<len-1的话是包括了i 不用加1
    }
}
int query(int l,int r){
    int len=r-l+1;
    int k=log(len)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]); //而r-1<<k是没有包含到r所以要+1
}
void solve() {
    cin>>n>>m;
    vector<int>a(m+10);
    int sum=0,mx=0;
    for(int i=1;i<=m;i++){
        cin>>a[i],sum+=a[i];
        mx=max(a[i]+i-1,mx);
        b[i]=a[i]+i-1;
    }
    if(sum<n||mx>n){cout<<-1<<endl;return;}
    init();
    vector<int>s(m+10);
    int now=0;
    for(int i=2;i<=m;i++){
        int need=n-query(i,m)-now;
        if(need>a[i-1]-1){
            s[i]+=a[i-1]-1;
            now+=s[i];
        }else{
            s[i]+=need;
            break;
        }
    }
    for(int i=1;i<=m;i++){
        s[i]+=s[i-1];
    }
    for(int i=1;i<=m;i++){
        cout<<s[i]+i<<' ';
    }cout<<endl;
}
signed main(){
    fast
    int t;t=1;//cin>>t;
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}

标签:631,const,10,int,Codeforces,aramis,板子,mx
From: https://www.cnblogs.com/ycllz/p/16835015.html

相关文章

  • Educational Codeforces Round 138 F Distance to the Path
    DistancetothePath思维+树链剖分首先与树链剖分无关,先考虑如果只更新一个点的情况因为更新一个点,它既能向根的方向更新,又能向子树方向更新,非常难维护,于是我们只......
  • Codeforces Round #829 (Div. 2)-C1
    C1题目链接:https://codeforces.com/contest/1754/problem/C1emmm,不知道怎么说,做的时候考虑的问题是我通过什么方法来划分整个数组使得题意成立,后面又困在怎么判断是否存......
  • Codeforces Round #707 (Div. 1, based on Moscow Open Olympiad in Informatics) A
    A.GoingHome观察ai<=2.5e6显然我们两数之和最多5e6我们开桶让后怎么暴力让我发愁了显然我们知道我们可能一个数被用了好多次这样显然不行可以想到就是把这个数对......
  • Codeforces Round #643 (Div. 2) C
    C.CountTriangles显然两边之和大于第三边我们可以先预处理出来这个两边之和我们暴力枚举x然后区间赋值[x+b,x+c]+1然后最后暴力枚举第三个边然后将大于第三边的方案......
  • Codeforces Round #673 (Div. 2) C. k-Amazing Numbers
    题面Youaregivenanarrayaconsistingofnintegersnumberedfrom1ton.Let’sdefinethek-amazingnumberofthearrayastheminimumnumberthatoccurs......
  • Codeforces Round #828 (Div. 3) A-F
    比赛链接A题解知识点:贪心,模拟。遇到没用过的数字就给个字母,遇到用过的数字就对照字母是否一致。时间复杂度\(O(n)\)空间复杂度\(O(n)\)代码#include<bits/stdc+......
  • Codeforces Round #632 (Div. 2) / 1333C】- C. Eugene and an array
    题面Eugenelikesworkingwitharrays.Andtodayheneedsyourhelpinsolvingonechallengingtask.Anarrayccisasubarrayofanarraybbifcccanbeobta......
  • Codeforces Round #725 (Div. 3) ABC(双指针)F
    https://codeforces.com/contest/1538AB都没啥好说的,C卡了半天,F挺好写的,找到规律了就直接ac1300的题目卡半天,1500的题目写的顺顺利利,真呆啊我A.StoneGame#include<......
  • Codeforces Round #619 (Motarack's Birthday)
    题面DarkisgoingtoattendMotarack’sbirthday.DarkdecidedthatthegiftheisgoingtogivetoMotarackisanarrayaofnnon-negativeintegers.Darkcr......
  • Codeforces Round #829 (Div. 2)
    Contest链接E题意简述给长为\(n\)序列,随机等概率交换两个不同位置(\(i<j\))的值,要求\(a_i>a_j\)时才能交换。\(n\le200000\)像这个题但是强制要求\(a......