제출 #1114640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114640		AdamGS	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	158 ms	7132 KiB

ho_t1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tr[1<<19];
int odp[200000];
void zm(int ind,int val){
    tr[ind]=val;
    ind/=2;
    while (ind>0){
        tr[ind]=max(tr[ind*2],tr[ind*2+1]);
        ind/=2;
    }
}
int main()
{
    int n,dltr=1;
    cin >> n;
    while (dltr<n) dltr*=2;
    vector<pair<int,int>> a(n+1);
    vector<int> b(n);
    for (int i=0; i<n+1; i++){
        cin >> a[i].first;
        a[i].second=i;
    }
    for (int i=0; i<n; i++) cin >> b[i];
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    //for (int i=0; i<n+1; i++) cout << a[i].first << ' ' << a[i].second << '\n';
    for (int i=0; i<n; i++) tr[dltr+i]=max(a[i+1].first-b[i],0);
    for (int i=dltr-1; 0<i; i--) tr[i]=max(tr[i*2],tr[i*2+1]);
    //for (int i=0; i<dltr*2; i++) cout << tr[i] <<' ';
    //cout << '\n';
    odp[a[0].second]=tr[1];
    for (int i=0; i<n; i++){
        zm(i+dltr,a[i].first-b[i]);
        //for (int i=0; i<dltr*2; i++) cout << tr[i] <<' ';
        //cout << '\n';
        odp[a[i+1].second]=tr[1];
    }
    for (int i=0; i<n+1; i++) cout << odp[i] << ' ';
    return 0;

}

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