Submission #285772

#	Time	Username	Problem	Language	Result	Execution time	Memory
285772		Fidisk	Just Long Neckties (JOI20_ho_t1)	C++14	0 / 100	1 ms	384 KiB

ho_t1

#include <bits/stdc++.h>
using namespace std;
 
#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)
#define _cos(xxxx) cos(xxxx*acos(-1)/180)
#define _sin(xxxx) sin(xxxx*acos(-1)/180)
#define _tan(xxxx) tan(xxxx*acos(-1)/180)
#define PE cout<<fixed
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
 
const ld pi=acos(-1);

ll n,i,a[500009],b[500009],segtree[3][2000009];

void init(ll type,ll id,ll l,ll r) {
    if (l!=r) {
        ll mid=(r+l)/2;
        init(type,id*2,l,mid);
        init(type,id*2+1,mid+1,r);
        segtree[type][id]=max(segtree[type][id*2],segtree[type][id*2+1]);
    }
    else {
        if (type==1) {
            segtree[type][id]=max(a[l+1]-b[l],l-l);
        }
        else {
            segtree[type][id]=max(a[l]-b[l],l-l);
        }
    }
}

ll getmax(ll type,ll id,ll l,ll r,ll u,ll v) {
    if ((l>r)||(r<u)||(l>v)) {
        return 0;
    }
    if ((l>=u)&&(r<=v)) {
        return segtree[type][id];
    }
    ll mid=(r+l)/2;
    return max(getmax(type,id*2,l,mid,u,v),getmax(type,id*2+1,mid+1,r,u,v));
}

int main() {
    IO;
    cin>>n;
    for (i=1;i<=n+1;i++) {
        cin>>a[i];
    }
    for (i=1;i<=n;i++) {
        cin>>b[i];
    }
    sort(a+1,a+n+2);
    sort(b+1,b+n+1);
    init(1,1,1,n);
    init(2,1,1,n);
    for (i=1;i<=n+1;i++) {
        cout<<max(getmax(1,1,1,n,i,n),getmax(2,1,1,n,1,i-1))<<' ';
    }
}
   

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