Submission #601439

#	Time	Username	Problem	Language	Result	Execution time	Memory
601439		Ozy	Snowball (JOI21_ho_t2)	C++17	100 / 100	105 ms	15368 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)

#define MAX 200000

lli der[MAX+2],izq[MAX+2],sum[MAX+2];
lli arr[MAX+2];
lli l,r,n,q,a,pos,dif,b;
lli res[MAX+2];

lli binaria(lli lim) {
    lli mitad,ini = 1;
    lli fin = q;
    lli ult = 0;
    while (ini <= fin) {
        mitad = (ini+fin)/2;
        if (sum[mitad] <= lim) {
            ult = mitad;
            ini = mitad+1;
        }
        else fin = mitad-1;
    }
    return ult;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    rep(i,1,n) cin >> arr[i];
    l = 0;
    r = 0;
    pos = 0;
    rep(i,1,q) {
        cin >> a;
        pos += a;
        der[i] = der[i-1];
        izq[i] = izq[i-1];

        if (pos > r) {
            der[i] += pos - r;
            r = pos;
        }
        else if (pos < l) {
            izq[i] += l - pos;
            l = pos;
        }
        sum[i] = der[i] + izq[i];
    }

    res[1] -= l;
    res[n] += r;
    rep(i,2,n) {
        dif = arr[i] - arr[i-1];
        a = binaria(dif);

        res[i-1] += der[a];
        res[i] += izq[a];

        if (a == q) continue;

        dif -= sum[a];
        a++;
        if (der[a-1] != der[a]) res[i-1] += dif;
        else res[i] += dif;
    }

    rep(i,1,n) cout << res[i] << "\n";
}

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