제출 #762947

#제출 시각아이디문제언어결과실행 시간메모리
762947vjudge1Just Long Neckties (JOI20_ho_t1)C++17
100 / 100
280 ms26252 KiB
#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;
      |             ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...