Submission #791636

#	Time	Username	Problem	Language	Result	Execution time	Memory
791636		n3rm1n	Snowball (JOI21_ho_t2)	C++17	100 / 100	104 ms	15372 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 2e5+10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, q;
long long a[MAXN], wind[MAXN];
long long moveleft[MAXN], moveright[MAXN];

void read()
{
    cin >> n >> q;
    for (long long i = 1; i <= n; ++ i)
        cin >> a[i];
    long long pos = 0;
    for (long long i = 1; i <= q; ++ i)
    {
        cin >> wind[i];
        pos += wind[i];
        moveleft[i] = min(pos, moveleft[i-1]);
        moveright[i] = max(pos, moveright[i-1]);
    }

    for (long long i = 1; i <= q; ++ i)
    {
        moveleft[i] *= -1;
       // cout << moveleft[i] << " " << moveright[i] << endl;
    }
}
long long ans[MAXN];
void solve()
{
    for (long long i = 2; i <= n; ++ i)
    {
      //  int f = 0;
        int l = 1, r = q, mid, x = q+1;
        while(l <= r)
        {
            mid = (l + r)/2;
            if(a[i-1] + moveright[mid] >= a[i] - moveleft[mid])
            {
                x = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        if(x != q+1)
        {


               // cout << "***" << endl;
               // cout << i-1 << " " << i << " " << j << endl;
                long long segment = a[i] - a[i-1];
                long long to_first = 0, to_second = 0;
                if(wind[x] >= 0)
                {
                    to_second = moveleft[x];
                    to_first = segment - to_second;
                }
                else
                {
                    to_first = moveright[x];
                    to_second = segment - to_first;
                }
                //cout << to_first << " " << to_second << endl;
                ans[i-1] += to_first;
                ans[i] += to_second;
        }
        else
         {
             ans[i-1] += moveright[q];
             ans[i] += moveleft[q];
         }


    }
    ans[1] += moveleft[q];
    ans[n] += moveright[q];
    for (long long i = 1; i <= n; ++ i)
        cout << ans[i] << " ";
    cout << endl;
}
int main()
{
    speed();

    read();
    solve();
    return 0;
}
/*

*/

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