Submission #1221949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221949		TadijaSebez	Snowball (JOI21_ho_t2)	C++20	100 / 100	82 ms	8364 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=200050;
ll x[N],ans[N];
int main(){
    int n,q;
    scanf("%i %i",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&x[i]);
    vector<pair<ll,ll>> pts;
    ll L=0,R=0,bal=0;
    pts.pb({0,0});
    for(int i=1;i<=q;i++){
        ll w;
        scanf("%lld",&w);
        bal+=w;
        if(bal>0)R=max(R,bal);
        else L=max(L,-bal);
        pts.pb({L,R});
    }
    ans[1]+=L;
    ans[n]+=R;
    for(int i=1;i<n;i++){
        ll dist=x[i+1]-x[i];
        int bot=1,top=(int)pts.size()-1,idx=-1;
        while(top>=bot){
            int mid=top+bot>>1;
            if(pts[mid].first+pts[mid].second>=dist){
                idx=mid;
                top=mid-1;
            }else{
                bot=mid+1;
            }
        }
        if(idx==-1){
            ans[i]+=R;
            ans[i+1]+=L;
        }else{
            ans[i]+=pts[idx-1].second;
            ans[i+1]+=pts[idx-1].first;
            ll diff=dist-pts[idx-1].first-pts[idx-1].second;
            if(pts[idx-1].first==pts[idx].first)ans[i]+=diff;
            else ans[i+1]+=diff;
        }
    }
    for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%i %i",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:11:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     for(int i=1;i<=n;i++)scanf("%lld",&x[i]);
      |                          ~~~~~^~~~~~~~~~~~~~
Main.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%lld",&w);
      |         ~~~~~^~~~~~~~~~~

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