Submission #533708

#	Time	Username	Problem	Language	Result	Execution time	Memory
533708		star_platinum	Snowball (JOI21_ho_t2)	C++14	100 / 100	105 ms	26284 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define mikumywaifu ios_base::sync_with_stdio(0)
#define mudrockmywaifu cin.tie(0)
#define pb push_back
#define ss second
#define ff first
#define mem(i,j) memset(i,j,sizeof(i))
#define pii pair<int,int>
#define pll pair<long,long>
#define lowbit(x) x&-x
const int INF =0x3F3F3F3F;
const ll LINF=4611686018426387903;
ll gcd(ll a,ll b){
    if(b==0) return a;
    a%=b;
    return gcd(b,a);
}
void debug(){
    cout<<"DEBUG :";
    cout<<"\n";
}
/*-----------------------------------------*/
struct l{
    ll id,v;  
};
bool cmp(l a,l b){
    return a.v<b.v;
}
signed main(){
    mikumywaifu;
    mudrockmywaifu;
    int n,q;
    cin>>n>>q;
    vector<ll> a(n+1),b(q+1);
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<q;i++) cin>>b[i];
    ll tmp=0;
    vector<vector<ll>>dp(q+1,vector<ll>(2,0));
    for(int i=1;i<=q;i++){
        tmp+=b[i-1];
        dp[i][0]=min(dp[i-1][0],tmp);
        dp[i][1]=max(dp[i-1][1],tmp);
    }
    vector<l>arr;
    for(int i=0;i<n-1;i++){
        arr.pb({i,a[i+1]-a[i]});
    }
    vector<ll> ans(n+1);
    sort(arr.begin(),arr.end(),cmp);
    int pos=0;
    if(n>1){
        for(int i=1;i<=q;i++){
            while(pos<arr.size()&&dp[i][1]-dp[i][0]>=arr[pos].v){
                  ans[arr[pos].id]+=dp[i-1][1];
                  ans[arr[pos].id+1]-=dp[i-1][0];
                  if(b[i-1]>0) ans[arr[pos].id]+=arr[pos].v-(dp[i-1][1]-dp[i-1][0]);
                  else ans[arr[pos].id+1]+=arr[pos].v-(dp[i-1][1]-dp[i-1][0]);
                  pos++;
                  if(pos>=n-1) break;
            }
        }
        for(int i=pos;i<n-1;i++){
            ans[arr[i].id]+=dp[q][1];
            ans[arr[i].id+1]-=dp[q][0];
        }
    }
    ans[n-1]+=dp[q][1];
    ans[0]-=dp[q][0];
    for(int i=0;i<n;i++){
        cout<<ans[i]<<"\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<l>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             while(pos<arr.size()&&dp[i][1]-dp[i][0]>=arr[pos].v){
      |                   ~~~^~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67