Submission #1047956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047956		DeathIsAwe	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	239 ms	38336 KiB

ho_t1

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


int main() {
    int n; cin >> n;
    vector<int> newties(n+1), oldties(n), unsortednew;
    unordered_map<int,ll> ansmap, strange;
    for (int i=0;i<n+1;i++) {
        cin >> newties[i];
    }
    for (int i=0;i<n;i++) {
        cin >> oldties[i];
    }
    unsortednew = newties;


    sort(newties.begin(), newties.end());
    sort(oldties.begin(), oldties.end());
    priority_queue<ll> lol;
    ll ans = 0, dummy;
    for (int i=0;i<n;i++) {
        dummy = max(newties[i+1] - oldties[i], 0);
        if (strange.find(dummy) != strange.end()) {
            strange[dummy] += 1;
        } else {
            strange[dummy] = 1;
            lol.push(dummy);
        }
    }
    ansmap[newties[0]] = lol.top();
    for (int i=0;i<n;i++) {
        dummy = max(newties[i+1] - oldties[i], 0);
        strange[dummy] -= 1;
        dummy = max(newties[i] - oldties[i], 0);
        if (strange.find(dummy) != strange.end()) {
            strange[dummy] += 1;
        } else {
            strange[dummy] = 1;
            lol.push(dummy);
        }
        while (strange[lol.top()] == 0) {
            lol.pop();
        }
        ansmap[newties[i+1]] = lol.top();
    }
    for (int i=0;i<n+1;i++) {
        cout << ansmap[unsortednew[i]] << ' ';
    }
}

Compilation message (stderr)

ho_t1.cpp: In function 'int main()':
ho_t1.cpp:22:8: warning: unused variable 'ans' [-Wunused-variable]
   22 |     ll ans = 0, dummy;
      |        ^~~

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