oj.uz

Submission #1115187

# Submission time Handle Problem Language Result Execution time Memory
1115187 2024-11-20T08:12:53 Z staszic_ojuz Just Long Neckties (JOI20_ho_t1) C++17
0 / 100
 1 ms 336 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

struct dat {
    ll a;
    ll i;
    dat(): a(0), i(0) {};
};
bool operator<(dat a, dat b) {
    return a.a < b.a;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n; cin >> n;
    vector<dat> wol(n + 1);
    for(int i = 0; i < n + 1; i++) {
        cin >> wol[i].a;
        wol[i].i = i;
    }
    vector<ll> ma(n);
    for(int i = 0; i < n; i++) {
        cin >> ma[i];
    }
    
    sort(wol.begin(), wol.end());
    sort(ma.begin(), ma.end());

    
    vector<dat> par1(n);
    vector<dat> par2(n);
    for(int i = 0; i < n; i++) {
        par1[i].i = wol[i].i;
        par1[i].a = max(wol[i].a - ma[i], (ll)0);
        par2[i].i = wol[i + 1].i;
        par2[i].a = max(wol[i + 1].a - ma[i], (ll)0);
    }
    vector<dat> pref(n + 2);
    vector<dat> suff(n + 2);
    pref[0].a = 0;
    pref[n + 1].a = 0;
    
    suff[0].a = 0;
    suff[n + 1].a = 0;    
    pref[0].i = par2[n - 1].i;
    for(int i = 1; i < n + 1; i++) {
        if(pref[i - 1].a > par1[i - 1].a) {
            pref[i].a = pref[i - 1].a;
        } else {
            pref[i].a = par1[i - 1].a;    
        }

        pref[i].i = par1[i - 1].i;
    }
    suff[n].i = par1[0].i;
    for(int i = n -1;i>=0;i--) {
        if(suff[i + 1].a > par2[i].a) {
            suff[i].a = suff[i + 1].a;
        } else {
            suff[i].a = par2[i].a;    
        }
        suff[i].i = par2[i].i;
    }
    // cout << "PAR!\n";
    // for(int i = 0; i < n; i++) {
    //     cout << par1[i].a << " " << par1[i].i << '\n';
    // }
    // cout << "Par2\n";
    // for(int i = 0; i < n; i++) {
    //     cout << par2[i].a << " " << par2[i].i << '\n';
    // }
    // cout << "PREF\n";
    // for(int i = 0; i < n + 1; i++) {
    //     cout << pref[i].a << " " << pref[i].i << '\n';
    // }
    // cout << "SUFF\n";
    // for(int i = 0; i < n + 1; i++) {
    //     cout << suff[i].a  << " " << suff[i].i << '\n';
    // }
    // cout << "WOL\n";
    // for(int i = 0; i < n + 1; i++) {
    //     cout << wol[i].a << " " << wol[i].i << '\n';
    // }

    vector<ll> pout(n + 1, 0);
    for(int i = 0; i < n + 1; i++) {
        pout[pref[i].i] = i;
    }

    // cout << "pout\n";
    // for(int i = 0; i < n + 1; i++) {
    //     cout << pout[i] << '\n';
    // }

    for(int i = 0; i < n + 1; i++) {
        //cout   << "pout[i]: " << pout[i] <<", i: " << i << "pout: "<< pout[i] << endl;
        ll res = pref[pout[i]].a;
        if (pout[i] > 0) {
            res =max(pref[pout[i] - 1].a, suff[pout[i] - 1].a);
        } else {
            res = max(pref[pout[n]].a, suff[n].a);
        }
        cout << res << " ";
    }

    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 91.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB Output isn't correct
7 Halted 0 ms 0 KB -