Submission #1165024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165024		attky	Snowball (JOI21_ho_t2)	C++20	100 / 100	53 ms	9800 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct ecart {
    int diff, pos;
    bool operator< (ecart other) {
        return diff < other.diff;
    }
};

struct inter {
    int deb, fin;

    inter update(int a) {
        return {min(deb, a), max(fin, a)};
    }

    int size() {
        return fin - deb;
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    int snowball[n+2];
    snowball[0] = -1e18;
    snowball[n+1] = 1e18;
    for(int loop = 0; loop < n; ++loop) {
        cin >> snowball[loop+1];
    }
    ecart ec[n+1];
    for(int loop = 0; loop < n+1; ++loop) {
        ec[loop] = {snowball[loop+1] - snowball[loop], loop};
    }
    inter deplacement = {0, 0};
    int pos = 0, i = 0;
    inter area[n+1];
    for(int loop = 0; loop < n+1; ++loop) {
        area[loop] = {1000000000000000000, 1000000000000000000};
    }
    sort(ec, ec + n + 1);
    for(int loop = 0; loop < q; ++loop) {
        int w;
        cin >> w;
        pos += w;
        inter newDepl = deplacement.update(pos);
        int s = newDepl.size();
        while(ec[i].diff < s) {
            int modif = ec[i].pos;
            if(w > 0) {
                area[modif+1].deb = deplacement.deb;
                area[modif].fin = ec[i].diff + deplacement.deb;
            }
            else {
                area[modif].fin = deplacement.fin;
                area[modif+1].deb = deplacement.fin - ec[i].diff;
            }
            i++;
        }
        deplacement = newDepl;
    }
    for(int loop = 0; loop < n+1; ++loop) {
        if(area[loop].deb == 1000000000000000000) {
            area[loop].deb = deplacement.deb;
        }
        if(area[loop].fin == 1000000000000000000) {
            area[loop].fin = deplacement.fin;
        }
    }
    for(int loop = 1; loop < n+1; ++loop) {
        cout << area[loop].fin - area[loop].deb << '\n';
    }
}

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