Submission #217872

#	Time	Username	Problem	Language	Result	Execution time	Memory
217872		KoalaMuch	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	168 ms	11384 KiB

ho_t1

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int ans[N];
int sm[N*4];
pair< int,int > a[N];
int b[N];
void build(int l,int r,int now)
{
    if(l==r)    {sm[now] = max(a[l+1].first-b[l],0);return;}
    int mid = (l+r) >> 1;
    build(l,mid,now<<1),build(mid+1,r,now<<1|1);
    sm[now] = max(sm[now<<1],sm[now<<1|1]);;
}
void upd(int l,int r,int idx,int now)
{
    if(l>idx||r<idx)    return ;
    if(l==r)    {sm[now] = max(0,a[l].first-b[l]);return ;}
    int mid = (l+r) >> 1;
    upd(l,mid,idx,now<<1),upd(mid+1,r,idx,now<<1|1);
    sm[now] = max(sm[now<<1],sm[now<<1|1]);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n+1;i++)   scanf("%d",&a[i].first),a[i].second = i;
    for(int i=1;i<=n;i++)   scanf("%d",&b[i]);
    sort(a+1,a+n+2),sort(b+1,b+n+1);
    build(1,n,1);
    ans[a[1].second] = sm[1];
    for(int i=1;i<=n;i++)
    {
        upd(1,n,i,1);
        ans[a[i+1].second] = sm[1];
    }
    for(int i=1;i<=n+1;i++) printf("%d ",ans[i]);
    return 0;
}

Compilation message (stderr)

ho_t1.cpp: In function 'int main()':
ho_t1.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
ho_t1.cpp:27:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n+1;i++)   scanf("%d",&a[i].first),a[i].second = i;
                               ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
ho_t1.cpp:28:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)   scanf("%d",&b[i]);
                             ~~~~~^~~~~~~~~~~~

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