제출 #1011961

#제출 시각아이디문제언어결과실행 시간메모리
1011961vantamSjeckanje (COCI21_sjeckanje)C++17
15 / 110
2040 ms604 KiB
#include<bits/stdc++.h> using namespace std; const int N=1005 ; long long i,j,n,q,type,l,r,x,ma,mi,lt,rt; long long a[200005],dp[200005] ; long long si[4*N],sa[4*N],st[4*N],s[4*N],lzi[4*N],lza[4*N]; pair<int,long long> lz[4*N]; int fi[N], fa[N] ; deque<int> qq ; void up(int id, int l, int r, int u, long long x){ if(r<u || u<l) return ; if(l==r){ s[id]=x ; return ; } int mid=(l+r)/2 ; up(2*id,l,mid,u,x) ; up(2*id+1,mid+1,r,u,x) ; s[id]=max(s[2*id], s[2*id+1]) ; return ; } void fixi(int id, int l, int r){ if(lzi[id]==ma) return ; si[id]=s[id]-lzi[id] ; if(l!=r){ lzi[2*id]=lzi[id] ; lzi[2*id+1]=lzi[id] ; } lzi[id]=ma ; return ; } void upi(int id, int l, int r, int u, int v, long long x){ fixi(id,l,r) ; if(r<u || v<l) return ; if(u<=l && r<=v){ lzi[id]=x ; fixi(id,l,r) ; return ; } int mid=(l+r)/2 ; upi(2*id,l,mid,u,v,x) ; upi(2*id+1,mid+1,r,u,v,x) ; si[id]=max(si[2*id], si[2*id+1]) ; return ; } void fixa(int id, int l, int r){ if(lza[id]==ma) return ; sa[id]=s[id]+lza[id] ; if(l!=r){ lza[2*id]=lza[id] ; lza[2*id+1]=lza[id] ; } lza[id]=ma ; return ; } void upa(int id, int l, int r, int u, int v, long long x){ fixa(id,l,r) ; if(r<u || v<l) return ; if(u<=l && r<=v){ lza[id]=x ; fixa(id,l,r) ; return ; } int mid=(l+r)/2 ; upa(2*id,l,mid,u,v,x) ; upa(2*id+1,mid+1,r,u,v,x) ; sa[id]=max(sa[2*id], sa[2*id+1]) ; return ; } void fixx(int id,int l, int r,int u, int v,int ii){ if(ii==1) fixa(id,l,r) ; else fixi(id,l,r) ; if(l==u && r==v) return ; int mid=(l+r)/2 ; if(v<=mid){ fixx(2*id,l,mid,u,v,ii) ; }else{ fixx(2*id+1,mid+1,r,u,v,ii) ; } } void fix(int id,int l, int r){ if(lz[id].second==ma) return ; if(lz[id].first==1){ fixx(1,1,n,l,r,1) ; st[id]=sa[id]-lz[id].second ; }else{ fixx(1,1,n,l,r,2) ; st[id]=si[id]+lz[id].second; } if(l!=r){ lz[2*id]=lz[id] ; lz[2*id+1]=lz[id] ; } lz[id].second=ma ; return ; } void upd(int id, int l, int r, int u, int v,int ii, long long x){ fix(id,l,r) ; if(r<u || v<l) return ; if(u<=l && r<=v){ lz[id]={ii,x} ; fix(id,l,r) ; return ; } int mid=(l+r)/2 ; upd(2*id,l,mid,u,v,ii,x) ; upd(2*id+1,mid+1,r,u,v,ii,x) ; st[id]=max(st[2*id], st[2*id+1]) ; return ; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); #define NAME "test" if(fopen(NAME".inp", "r")){ freopen(NAME".inp", "r", stdin); freopen(NAME".out", "w", stdout); } cin >> n >> q; for(i=1;i<=n;i++) cin >> a[i] ; //if(n*q<=1000000){ while(q--){ //cin >> type ; // if(type==1){ cin >> l >> r >> x ; for(i=l;i<=r;i++) a[i]+=x ; //}else{ // if(n*n*q<=10000000){ dp[0]=0 ; for(i=1;i<=n;i++){ ma=a[i]; mi=a[i]; dp[i]=-1e18; for(j=i;j>=1;j--){ ma=max(ma,a[j]) ; mi=min(mi,a[j]) ; dp[i]=max(dp[i], dp[j-1]+ma-mi) ; } } cout << dp[n] << '\n' ; // }else{ // ma=-2000000000000000 ; // for(i=0;i<=4*n;i++){ // lz[i].second=ma ; // si[i]=ma ; // sa[i]=ma; // st[i]=ma; // s[i]=ma; // lzi[i]=ma; // lza[i]=ma; // } // qq.clear() ; // for(i=1;i<=n;i++){ // while(!qq.empty() && a[qq.front()]<=a[i]) qq.pop_front() ; // if(!qq.empty()) fa[i]=qq.front()+1 ; // else fa[i]=i ; // qq.push_back(i) ; // } // qq.clear() ; // for(i=1;i<=n;i++){ // while(!qq.empty() && a[qq.front()]>=a[i]) qq.pop_front() ; // if(!qq.empty()) fi[i]=qq.front()+1 ; // else fi[i]=i ; // qq.push_back(i) ; // } // dp[0]=0 ; // dp[1]=0 ; // up(1,0,n-1,0,0) ; // up(1,0,n-1,1,0) ; // upi(1,1,n,1,1,a[1]) ; // upa(1,1,n,1,1,a[1]) ; // upd(1,1,n,1,1,1,a[1]) ; // for(i=2;i<=n;i++){ // if(fa[i]!=fi[i]){ // if(fa[i]<fi[i]){ // lt=fa[i] ; // rt=fi[i] ; // upa(1,1,n,lt,rt-1,a[i]) ; // upd(1,1,n,lt,rt-1,2,a[i]) ; // }else{ // lt=fi[i] ; // rt=fa[i] ; // upi(1,1,n,lt,rt-1,a[i]) ; // upd(1,1,n,lt,rt-1,1,a[i]) ; // } // } // fix(1,1,n) ; // dp[i]=st[1] ; // up(1,0,n-1,i,dp[i]) ; // } // cout << dp[n] << '\n' ; // } } // } // } return 0; } /* 4 7 -1 3 -6 8 1 4 4 2 2 1 4 4 3 2 1 1 2 -1 1 1 2 -4 2 */

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

Main.cpp: In function 'int main()':
Main.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...