Submission #1211945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211945		minhpk	Snowball (JOI21_ho_t2)	C++20	100 / 100	69 ms	9800 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int z[1000005];
int pos[1000005];
pair<int,int> pre[1000005];
int t[1000005];
int cur=0;
int res[1000005];

void check(int x,int y){

    int dist=z[y]-z[x];
    int l=1;
    int r=b;
    int pos=0;
    while (l<=r){
           int mid=(l+r)/2;
           int predist=abs(pre[mid].first)+pre[mid].second;
           if (predist<=dist){
               pos=mid;
               l=mid+1;
           }else{
               r=mid-1;
           }
    }
    //cout << pos << " ";
   // cout << pos << " ";
    res[x]+=abs(pre[pos].second);
    res[y]+=abs(pre[pos].first);
    int remain=dist-abs(pre[pos].first)-abs(pre[pos].second);
    if (pos==b || remain==0){
        return;
    }
    if (t[pos+1]>=0){
        res[x]+=remain;
    }else{
        res[y]+=remain;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=a;i++){
         cin >> z[i];
    }
    for (int i=1;i<=b;i++){
         cin >> t[i];
         cur+=t[i];
         pre[i]=pre[i-1];
         pre[i].first=min(pre[i].first,cur);
         pre[i].second=max(pre[i].second,cur);
    }

    res[1]+=abs(pre[b].first);
    res[a]+=abs(pre[b].second);

  //  for (int i=1;i<=b;i++){
    //     cout << pre[i].first << " " <<  pre[i].second << "\n";
  //  }

    for (int i=2;i<=a;i++){
         check(i-1,i);
    }
  //  cout << "\n";

    for (int i=1;i<=a;i++){
         cout << res[i] << "\n";
    }
    return 0;
}

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