Submission #1180473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180473		bbartek	Snowball (JOI21_ho_t2)	C++20	100 / 100	71 ms	9872 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define st first
#define nd second
#define pb push_back

const int maxn = 2e5+7;

ll pozycje[maxn];
ll zebrane[maxn];
ll dodatnie[maxn];
ll ujemne[maxn];
ll wynik[maxn];
ll bil[maxn];

int binsearch(int pocz,int kon,ll val){
    int sro;
    while(pocz < kon){
        sro = (pocz+kon)/2;
        if(dodatnie[sro] + ujemne[sro] < val){
            pocz = sro+1;
        }
        else{
            kon = sro;
        }
    }
    return pocz;
}

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

    int n,q;
    cin>>n>>q;

    ll a;
    for(int i=1;i<=n;i++){
        cin>>a;
        pozycje[i] = a;
    }

    ll bilans = 0;
    for(int i=1;i<=q;i++){
        cin>>a;
        bilans += a;
        bil[i] = bilans;
        if(bilans > dodatnie[i-1]){
            dodatnie[i] = bilans;
        }
        else{
            dodatnie[i] = dodatnie[i-1];
        }
        if(bilans < -ujemne[i-1]){
            ujemne[i] = -bilans;
        }
        else{
            ujemne[i] = ujemne[i-1];
        }
    }

    pozycje[0] = -2e18;
    pozycje[n+1] = 2e18;

    ll dlu;
    int x;
    for(int i=0;i<=n;i++){
        dlu = pozycje[i+1] - pozycje[i];
        x = binsearch(0,q,dlu);
        if(bil[x] > bil[x-1]){
            wynik[i] += min(dlu-ujemne[x],dodatnie[x]);
            wynik[i+1] += ujemne[x];
            //cout<<i<<" "<<min(dlu-ujemne[x],dodatnie[x])<<" dodatnie\n";
            //cout<<i+1<<" "<<ujemne[x]<<" ujemne\n";
        }
        else{
            wynik[i] += dodatnie[x];
            wynik[i+1] += min(dlu-dodatnie[x],ujemne[x]);
            //cout<<i<<" "<<dodatnie[x]<<" dodatnie\n";
            //cout<<i+1<<" "<<min(dlu-dodatnie[x],ujemne[x])<<" ujemne\n";
        }
    }

    for(int i=1;i<=n;i++){
        cout<<wynik[i]<<"\n";
    }

    return 0;
}

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