oj.uz

Submission #285772

# Submission time Handle Problem Language Result Execution time Memory
285772 2020-08-29T15:03:59 Z Fidisk Just Long Neckties (JOI20_ho_t1) C++14
0 / 100
 1 ms 384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 91.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -