Submission #867328

#	Time	Username	Problem	Language	Result	Execution time	Memory
867328		EthanKim8683	Snowball (JOI21_ho_t2)	C++17	100 / 100	83 ms	25032 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=200000;
const I Q=200000;
Lli x_arr[N];
Lli w_arr[Q];
vector<tuple<Lli,I,I,Lli>>upds;
vector<tuple<Lli,I,I>>qrys;
Lli ress[N];
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n,q;cin>>n>>q;
  for(I i=0;i<n;i++)cin>>x_arr[i];
  for(I i=0;i<q;i++)cin>>w_arr[i];
  Lli acc=0,suf=0,pre=0;
  for(I i=0;i<q;i++){
    Lli w=w_arr[i];
    acc+=w;
    if(w>0){
      pre=max(pre,acc);
      upds.push_back({pre+suf,i,1,suf});
    }
    if(w<0){
      suf=max(suf,-acc);
      upds.push_back({pre+suf,i,0,pre});
    }
  }
  for(I i=0;i+1<n;i++)qrys.push_back({x_arr[i+1]-x_arr[i],i,i+1});
  sort(upds.rbegin(),upds.rend());
  sort(qrys.rbegin(),qrys.rend());
  I t1=2;
  Lli len1;
  for(I i=0,j=0;i<qrys.size();i++){
    auto[wid1,l,r]=qrys[i];
    for(;j<upds.size();j++){
      auto[wid2,k,t2,len2]=upds[j];
      if(wid2<wid1)break;
      tie(t1,len1)=tie(t2,len2);
    }
    if(t1==0){
      ress[l]+=len1;
      ress[r]+=max(wid1-len1,0ll);
    }
    if(t1==1){
      ress[l]+=max(wid1-len1,0ll);
      ress[r]+=len1;
    }
    if(t1==2){
      ress[l]+=pre;
      ress[r]+=suf;
    }
  }
  ress[0]+=suf;
  ress[n-1]+=pre;
  for(I i=0;i<n;i++)printf("%lli\n",ress[i]);
}

Compilation message (stderr)

Main.cpp: In function 'I main()':
Main.cpp:35:18: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<std::tuple<long long int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(I i=0,j=0;i<qrys.size();i++){
      |                 ~^~~~~~~~~~~~
Main.cpp:37:11: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<std::tuple<long long int, int, int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(;j<upds.size();j++){
      |          ~^~~~~~~~~~~~
Main.cpp:48:14: warning: 'len1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |       ress[r]+=len1;
      |       ~~~~~~~^~~~~~

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