제출 #636278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636278		Piokemon	Snowball (JOI21_ho_t2)	C++17	100 / 100	115 ms	16880 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long int
constexpr ll oo = 4611686018427387904;
ll naj_lewo[200009];
ll naj_prawo[200009];
ll ter[200009];
ll wiatr[200009];
ll poz[200009];
ll odp[200009];

int bin_ser(int pocz, int kon, ll szuk){
    int srod;
    while(pocz<kon){
        srod = (pocz+kon+1)/2;
        if (naj_prawo[srod]-naj_lewo[srod] > szuk){
            kon = srod-1;
        }
        else{
            pocz = srod;
        }
    }
    return pocz;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q,dokl;
    ll dyst;
    cin >> n >> q;
    for (int x=1;x<=n;x++){
        cin >> poz[x];
    }
    ter[0] = 0;
    for (int x=1;x<=q;x++){
        cin >> wiatr[x];
        ter[x] = ter[x-1] + wiatr[x];
        naj_lewo[x] = min(naj_lewo[x-1],ter[x]);
        naj_prawo[x] = max(naj_prawo[x-1],ter[x]);
    }
    for (int x=1;x<n;x++){
        dyst = poz[x+1]-poz[x];
        dokl = bin_ser(0,q,dyst);
        odp[x] += naj_prawo[dokl];
        odp[x+1] += -naj_lewo[dokl];
        if (dokl < q){
            if (wiatr[dokl+1]>0){
                odp[x] += dyst-naj_prawo[dokl]+naj_lewo[dokl];
            }
            else{
                odp[x+1] += dyst-naj_prawo[dokl]+naj_lewo[dokl];
            }
        }
    }
    odp[1] += -naj_lewo[q];
    odp[n] += naj_prawo[q];
    for (int x=1;x<=n;x++){
        cout << odp[x] << "\n";
    }
    return 0;
}

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