Submission #643674

#	Time	Username	Problem	Language	Result	Execution time	Memory
643674		Richem	Snowball (JOI21_ho_t2)	C++14	100 / 100	578 ms	15316 KiB

Main

#include <iostream>
#include <vector>
#define int long long
using namespace std;

const int MAX_NOMBRE = 2e5+42, INF = 1e13;

int nbBoule, nbVent;

int pos[MAX_NOMBRE];
int vent[MAX_NOMBRE][2] = {0};

int rep[MAX_NOMBRE][2] = {0};

void input() {
    cin >> nbBoule >> nbVent;

    for(int i = 0; i < nbBoule; i++)
        cin >> pos[i];

    int cumul = 0;
    for(int i = 0; i < nbVent; i++) {
        int curVent;
        cin >> curVent;

        cumul += curVent;

        if(i > 0) {
            vent[i][0] = min(vent[i-1][0], cumul);
            vent[i][1] = max(vent[i-1][1], cumul);
        }
        else {
            if(cumul < 0) vent[i][0] = cumul;
            else vent[i][1] = cumul;
        }
    }

    rep[0][0] = -vent[nbVent-1][0];
    rep[nbBoule-1][1] = vent[nbVent-1][1];
}


bool possible(int idBoule, int curEtape, int cote) {
    if((cote == 0 && idBoule == 0) || (cote == 1 && idBoule == nbBoule-1)) 
        return 1;

    //cout << curEtape << " COTE \n";

    //if(idBoule == 1 && curEtape == 0 && cote == 1) cout << " YIOUPU";

    int bordCur = pos[idBoule] + vent[curEtape][cote];
    int diff[2] = {-1, 1};

    int idAutre = idBoule + diff[cote];

    int bordAutre = pos[idAutre] + vent[curEtape][1 - cote];

    if(cote == 0) {
        rep[idBoule][cote] = max(rep[idBoule][cote], pos[idBoule] - max(bordCur, bordAutre));
    }
    else {
        rep[idBoule][cote] = max(rep[idBoule][cote], min(bordCur, bordAutre) - pos[idBoule]);
        //cout << rep[idBoule][cote] << " REP \n";
    }

    //cout << pos[idBoule] << " " << bordCur << " " << pos[idBoule + diff[cote]] << " " << bordAutre << endl;

    bool ok = ((max(bordAutre, pos[idAutre]) <= min(pos[idBoule], bordCur)) || (max(bordCur, pos[idBoule]) <= min(pos[idAutre], bordAutre)));

    return ok;
}

void dicho(int idBoule, int cote) {
    int deb = 0, fin = nbVent-1;

    int ah = 0;

    while(deb <= fin) {
        int milieu = (deb + fin+1) / 2;

        if(possible(idBoule, milieu, cote)) 
            deb = milieu;
        else
            fin = milieu-1;

        if(deb == fin) {
            ah++;
            if(ah > 1) return;
        }
    }
}

signed main() {
    input();

    /*
    dicho(1, 1);
    return 0;
    while(1) {
        int a,b,c;
        cin >> a >> b >> c;

        cout << possible(a,b,c) << endl;
    }
    */


    for(int cur = 0; cur < nbBoule; cur++) {
        dicho(cur, 0);
        dicho(cur, 1);

        cout << rep[cur][0] + rep[cur][1] << endl;
    }
}

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