제출 #762947

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

ho_t1

#include<bits/stdc++.h>
using namespace std;

#define taskname "template"
#define ll long long
#define ld double
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int,int> 
#define vii vector<pii>
#define vvi vector<vi>
#define pb push_back
#define eb emplace_back

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MN=2e5+5;

int n;
pair<ll,int> new_arr[MN+1];
ll arr[MN];//the value is new_arr[i]-arr[i]
ll arr2[MN+1];
map<int,int> mp;
ll left_st[MN<<2],right_st[MN<<2];//not update and update

void build(int id,int l,int r){
    if(l==r){
        left_st[id]=arr[l];
        right_st[id]=arr2[l];
        /*
        cout<<"Case "<<l<<' '<<r<<": \n";
        cout<<"left: "<<left_st[id]<<'\n';
        cout<<"right: "<<right_st[id]<<'\n';
        */
        return;
    }
    int mid=l+r>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);

    left_st[id]=max(left_st[id<<1],left_st[id<<1|1]);
    right_st[id]=max(right_st[id<<1],right_st[id<<1|1]);
    /*
    cout<<"Case "<<l<<' '<<r<<": \n";
    cout<<"left: "<<left_st[id]<<'\n';
    cout<<"right: "<<right_st[id]<<'\n';
    */
}

ll get_left(int id,int l,int r,int tl,int tr){
    if(tl>tr) return (ll)0;
    if(tl>r||l>tr) return (ll)0;
    if(tl<=l&&r<=tr) return left_st[id];

    int mid=l+r>>1;
    ll get1=get_left(id<<1,l,mid,tl,tr);
    ll get2=get_left(id<<1|1,mid+1,r,tl,tr);

    return max(get1,get2);
}

ll get_right(int id,int l,int r,int tl,int tr){
    if(tl>tr) return (ll)0;
    if(tl>r||l>tr) return (ll)0;
    if(tl<=l&&r<=tr) return right_st[id];

    int mid=l+r>>1;
    ll get1=get_right(id<<1,l,mid,tl,tr);
    ll get2=get_right(id<<1|1,mid+1,r,tl,tr);

    return max(get1,get2);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    /*
    freopen(taskname".inp","r",stdin);
    freopen(taskname".out","w",stdout);
    */

    cin>>n;
    for(int i=1;i<=n+1;++i){
        cin>>new_arr[i].fi;
        new_arr[i].se=i;
    }
    for(int i=1;i<=n;++i){
        cin>>arr[i];
    }
    sort(arr+1,arr+1+n);
    sort(new_arr+1,new_arr+1+n+1);

    for(int i=1;i<=n+1;++i){
        mp[new_arr[i].se]=i;
    }
    
    for(int i=2;i<=n+1;++i){
        arr2[i]=max((ll)0,new_arr[i].fi-arr[i-1]);
    }
    for(int i=1;i<=n;++i){
        arr[i]=max((ll)0,new_arr[i].fi-arr[i]);
    }
    /*
    for(int i=1;i<=n+1;++i){
        cout<<arr2[i]<<' ';
    }
    */
    build(1,1,n+1);

    for(int i=1;i<=n+1;++i){
        int idx=mp[i];
        ll get1=get_left(1,1,n+1,1,idx-1);
        ll get2=get_right(1,1,n+1,idx+1,n+1);
        cout<<max(get1,get2)<<' ';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t1.cpp: In function 'void build(int, int, int)':
ho_t1.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid=l+r>>1;
      |             ~^~
ho_t1.cpp: In function 'long long int get_left(int, int, int, int, int)':
ho_t1.cpp:56:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     int mid=l+r>>1;
      |             ~^~
ho_t1.cpp: In function 'long long int get_right(int, int, int, int, int)':
ho_t1.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |     int mid=l+r>>1;
      |             ~^~

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