Submission #364637

#	Time	Username	Problem	Language	Result	Execution time	Memory
364637		cpp219	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	606 ms	21484 KiB

ho_t1

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e5 + 6;
const ll inf = 1e9 + 7;
typedef pair<int,int> LL;
LL A[N];
ll n,b[N],a[N],ans[N],init,diff[N],Dec,cur;

bool chk(ll m,ll st){
    for (ll i = 1;i <= n;i++){
        ll nxt = upper_bound(a + 1,a + n + 2,b[i] + m) - a - 1;
        if (nxt >= st) nxt--;
        if (nxt < i) return 0;
    }
    return 1;
}

ll bs(ll st){
    ll l,m,h; l = 0; h = inf;
    while(l <= h){
        m = (l + h)/2;
        if (chk(m,st)) h = m - 1;
        else l = m + 1;
    }
    return l;
}
set<LL> s;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n;
    for (ll i = 1;i <= n + 1;i++) cin>>A[i].fs,A[i].sc = i; sort(A + 1,A + n + 2);
    for (ll i = 1;i <= n + 1;i++) a[i] = A[i].fs;
    for (ll i = 1;i <= n;i++) cin>>b[i]; sort(b + 1,b + n + 1);
    init = cur = bs(1); ans[A[1].sc] = cur;
    for (ll i = 1;i <= n;i++) diff[i] = b[i] - a[i + 1] + init,s.insert({diff[i],i});
    for (ll i = 2;i <= n + 1;i++){
        s.erase({diff[i - 1],i - 1}); diff[i - 1] = b[i - 1] - a[i - 1] + init;
        s.insert({diff[i - 1],i - 1});
        LL t = *s.begin();
        cur -= t.fs - Dec; Dec = t.fs; ans[A[i].sc] = cur;
    }
    for (ll i = 1;i <= n + 1;i++) cout<<ans[i]<<" ";
}

Compilation message (stderr)

ho_t1.cpp: In function 'int main()':
ho_t1.cpp:41:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   41 |     for (ll i = 1;i <= n + 1;i++) cin>>A[i].fs,A[i].sc = i; sort(A + 1,A + n + 2);
      |     ^~~
ho_t1.cpp:41:61: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   41 |     for (ll i = 1;i <= n + 1;i++) cin>>A[i].fs,A[i].sc = i; sort(A + 1,A + n + 2);
      |                                                             ^~~~
ho_t1.cpp:43:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   43 |     for (ll i = 1;i <= n;i++) cin>>b[i]; sort(b + 1,b + n + 1);
      |     ^~~
ho_t1.cpp:43:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |     for (ll i = 1;i <= n;i++) cin>>b[i]; sort(b + 1,b + n + 1);
      |                                          ^~~~
ho_t1.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   37 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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