Submission #866111

#	Time	Username	Problem	Language	Result	Execution time	Memory
866111		raphaelp	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	215 ms	10188 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<pair<int, int>> ties;
    vector<int> start(N);
    for (int i = 0; i <= N; i++)
    {
        int temp;
        cin >> temp;
        ties.push_back({temp, i});
    }
    for (int i = 0; i < N; i++)
    {
        cin >> start[i];
    }
    sort(start.begin(), start.end());
    sort(ties.begin(), ties.end());
    vector<int> ans(N + 1);
    deque<pair<int, int>> Q;
    for (int i = 1; i <= N; i++)
    {
        while (!Q.empty() && Q.back().first < max(ties[i].first - start[i - 1], 0))
            Q.pop_back();
        Q.push_back({max(ties[i].first - start[i - 1], 0), i - 1});
    }
    ans[ties[0].second] = Q.front().first;
    for (int i = 0; i < N; i++)
    {
        while (!Q.empty() && Q.front().second <= i)
            Q.pop_front();
        while (!Q.empty() && Q.back().first < max(ties[i].first - start[i], 0))
            Q.pop_back();
        Q.push_back({max(ties[i].first - start[i], 0), N + 10});
        ans[ties[i + 1].second] = Q.front().first;
    }
    for (int i = 0; i <= N; i++)
    {
        cout << ans[i] << ' ';
    }
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91