이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |