이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int MX = 5e5 + 5 ;
const pair<ll,ll> emp = {0,0} ;
pair<ll,ll> dp[MX] ;
struct lazytree
{
vector<pair<ll,ll> > t , lazy ;
void init(int n)
{
t = vector<pair<ll , ll> > (4*n + 4 , emp) ;
lazy = vector<pair<ll , ll> > (4*n + 4 , emp) ;
}
void upd(int node , pair<ll,ll> val)
{
t[node] = max(t[node],val) ;
lazy[node] = max(lazy[node],val) ;
}
void shift(int node , int low , int high)
{
int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
upd(left,lazy[node]) ;
upd(right,lazy[node]) ;
lazy[node] = emp ;
}
void update(int node , int low , int high , int l , int r , pair<ll,ll> val)
{
if(l>r) return ;
if((r<low) || (l>high)) return ;
if((l<=low) && (high<=r))
{
upd(node,val) ;
return ;
}
shift(node,low,high) ;
int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
update(left,low,mid,l,r,val) ;
update(right,mid+1,high,l,r,val) ;
t[node] = max(t[left],t[right]) ;
}
pair<ll,ll> query(int node , int low , int high , int l , int r)
{
if(l>r) return emp ;
if((r<low) || (l>high)) return emp ;
if((l<=low) && (high<=r)) return t[node] ;
shift(node,low,high) ;
int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
return max(query(left,low,mid,l,r),query(right,mid+1,high,l,r)) ;
}
};
int main()
{
int n ;
scanf("%d",&n) ;
ll a[n+2] , pref[n+2] = {0} ;
for(int i = 1 ; i <= n ; ++i)
{
scanf("%lld",&a[i]) ;
pref[i] += (pref[i-1]+a[i]) ;
}
lazytree T ;
T.init(n) ;
for(int i = 1 ; i <= n ; ++i)
{
pair<ll,ll> cur = {1,pref[i]} , qc = T.query(1,1,n,i,i) ;
cur = max(cur,{qc.first,pref[i]-qc.second}) ;
int low = 0 , high = n ;
while(low<high)
{
int mid = (low+high)>>1 ;
if((pref[mid]-pref[i])>=cur.second) high = mid ;
else low = mid + 1 ;
}
dp[i] = cur ;
T.update(1,1,n,low,n,{cur.first+1,pref[i]}) ;
}
printf("%lld\n",dp[n].first) ;
return 0 ;
}
컴파일 시 표준 에러 (stderr) 메시지
segments.cpp: In member function 'void lazytree::shift(int, int, int)':
segments.cpp:27:13: warning: unused variable 'mid' [-Wunused-variable]
27 | int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
| ^~~
segments.cpp: In function 'int main()':
segments.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d",&n) ;
| ~~~~~^~~~~~~~~
segments.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%lld",&a[i]) ;
| ~~~~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |