Submission #387385

#	Time	Username	Problem	Language	Result	Execution time	Memory
387385		uacoder123	Snowball (JOI21_ho_t2)	C++14	100 / 100	544 ms	18660 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
lli n,q;
lli a[200100],pos[200100];
vi sum(200100),po1(200100),ne1(200100);
vi v;
lli ans[200100];
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>n>>q;
  for(lli i=0;i<n;++i)
    cin>>pos[i];
  for(lli i=0;i<q;++i)
  {
    cin>>a[i];
    if(i!=0)
      a[i]=a[i]+a[i-1];
  }
  lli po=0,ne=0;
  for(lli i=0;i<q;++i)
  {
    if(a[i]>=0&&a[i]>=po)
    {
      v.pb(a[i]-po);
      po=a[i];
    }
    else if(a[i]<0&&a[i]<=ne)
    {
      v.pb(a[i]-ne);
      ne=a[i];
    }
  }
  lli n1=v.size();
  for(lli i=0;i<n1;++i)
  {
    sum[i+1]=abs(v[i]);
    if(v[i]>0)
      po1[i+1]=v[i];
    else
      ne1[i+1]=v[i];
    if(i>0)
    {
      sum[i+1]+=sum[i];
      po1[i+1]+=po1[i];
      ne1[i+1]+=ne1[i];
    }
  }
  for(lli i=1;i<n;++i)
  {
    lli l=pos[i]-pos[i-1];
    lli it=lower_bound(sum.begin()+1,sum.begin()+v.size()+1,l)-sum.begin();
    if(it==v.size()+1)
      it--;
    if(it-1<0)
      exit(1);
    ans[i-1]+=po1[it];
    ans[i]+=-ne1[it];
    if(v[it-1]>0)
      ans[i-1]-=max(0*1LL,(v[it-1]-(l-sum[it-1])));
    else
      ans[i]-=max(0*1LL,(-v[it-1]-(l-sum[it-1])));
  }
  ans[0]+=-ne1[n1];
  ans[n-1]+=po1[n1];
  for(lli i=0;i<n;++i)
    cout<<ans[i]<<endl;
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:70:10: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     if(it==v.size()+1)
      |        ~~^~~~~~~~~~~~

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