Submission #757626

#	Time	Username	Problem	Language	Result	Execution time	Memory
757626		HoriaHaivas	Snowball (JOI21_ho_t2)	C++14	100 / 100	122 ms	9768 KiB

Main

/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

int v[200001];
int rightmost[200001];
int leftmost[200001];
int weight[200001];
int w[200001];

bool intervaldone (int query, int pos)
{
     if (rightmost[query]+leftmost[query]>=v[pos+1]-v[pos])
         return 1;
     return 0;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,q,i,j,poz,r,pas;
    cin >> n >> q;
    for (i=1;i<=n;i++)
    {
         cin >> v[i];
    }
    poz=0;
    for (j=1;j<=q;j++)
    {
         cin >> w[j];
         poz+=w[j];
         rightmost[j]=max(rightmost[j-1],poz);
         leftmost[j]=min(leftmost[j-1],poz);
    }
    for (j=1;j<=q;j++)
         leftmost[j]=abs(leftmost[j]);
    weight[1]+=leftmost[q];
    weight[n]+=rightmost[q];
    for (j=1;j<n;j++)
    {
         r=0;
         pas=(1<<17);
         while (pas)
         {
             if (r+pas<=q && !intervaldone(r+pas,j))
                 r+=pas;
             pas=pas/2;
         }
         r++;
         if (r==q+1)
         {
             r--;
             weight[j]+=rightmost[q];
             weight[j+1]+=leftmost[q];
         }
        else if (rightmost[r]==rightmost[r-1])
         {
             weight[j]+=rightmost[r];
             weight[j+1]+=(v[j+1]-v[j])-rightmost[r];
         }
         else
         {
             weight[j+1]+=leftmost[r];
             weight[j]+=(v[j+1]-v[j])-leftmost[r];
         }
    }
    for (j=1;j<=n;j++)
    {
         cout << weight[j] << "\n";
    }
}

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