제출 #213061

#제출 시각아이디문제언어결과실행 시간메모리
213061Pajaraja별자리 3 (JOI20_constellation3)C++17
100 / 100
673 ms86776 KiB
#include <bits/stdc++.h> #define MAXN 200007 using namespace std; long long dp[MAXN],seg[4*MAXN]; int lc[40*MAXN],per[40*MAXN],mxb[MAXN],mnb[MAXN],rc[40*MAXN],dl[MAXN],dr[MAXN],h[MAXN],root[MAXN],cnt,n,m; struct star{int x,y; long long c;}; bool cmp(star a,star b) {return a.y<b.y;} star a[MAXN]; vector<int> zp[MAXN],zf[MAXN]; void updmxb(int x,int ind) { while(ind<MAXN) { mxb[ind]=max(mxb[ind],x); ind+=(ind&-ind); } } int nmax(int ind) { int val=0; while(ind) { val=max(val,mxb[ind]); ind-=(ind&-ind); } return val; } void updmnb(int x,int ind) { while(ind<MAXN) { mnb[ind]=min(mnb[ind],x); ind+=ind&-ind; } } int nmin(int ind) { int val=MAXN; while(ind) { val=min(val,mnb[ind]); ind-=(ind&-ind); } return val; } void updseg(int l,int r,int lt,int rt,long long v,int ind) { if(r<lt || l>rt) return; if(l>=lt && r<=rt) {seg[ind]+=v; return;} int s=(l+r)/2; updseg(l,s,lt,rt,v,2*ind); updseg(s+1,r,lt,rt,v,2*ind+1); } long long nsum(int l,int r,int t,int ind) { if(l==r) return seg[ind]; int s=(l+r)/2; if(s>=t) return seg[ind]+nsum(l,s,t,2*ind); return seg[ind]+nsum(s+1,r,t,2*ind+1); } void makeper(int l,int r,int ind) { per[ind]=m+1; if(l==r) return; int s=(l+r)/2; lc[ind]=++cnt; makeper(l,s,lc[ind]); rc[ind]=++cnt; makeper(s+1,r,rc[ind]); } void makenewper(int l,int r,int t,int val,int inh,int ind) { per[ind]=val; if(l==r) return; int s=(l+r)/2; if(t<=s) { rc[ind]=rc[inh]; lc[ind]=++cnt; makenewper(l,s,t,val,lc[inh],lc[ind]); } else { lc[ind]=lc[inh]; rc[ind]=++cnt; makenewper(s+1,r,t,val,rc[inh],rc[ind]); } } int fnd(int l,int r,int lt,int rt,int ind) { if(r<lt || l>rt) return MAXN; if(l>=lt && r<=rt) return per[ind]; int s=(l+r)/2; return min(fnd(l,s,lt,rt,lc[ind]),fnd(s+1,r,lt,rt,rc[ind])); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&h[i]); scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].c); sort(a+1,a+m+1,cmp); for(int i=1;i<=m;i++) zf[a[i].x].push_back(i); fill(mnb,mnb+MAXN,n+1); for(int i=1;i<=n;i++) { updmxb(i,n+1-h[i]); for(int j=0;j<zf[i].size();j++) dl[zf[i][j]]=nmax(n+1-a[zf[i][j]].y); } for(int i=n;i>=1;i--) { updmnb(i,n+1-h[i]); for(int j=0;j<zf[i].size();j++) dr[zf[i][j]]=nmin(n+1-a[zf[i][j]].y); } makeper(1,n,root[m+1]); for(int i=m;i>=1;i--) { root[i]=++cnt; makenewper(1,n,a[i].x,i,root[i+1],root[i]); } a[m+1].c=0; for(int i=1;i<=m+1;i++) { long long nc=nsum(1,n,a[i].x,1),ac=a[i].c; for(int j=0;j<zp[i].size();j++) {nc+=dp[zp[i][j]]; ac+=dp[zp[i][j]];} dp[i]=min(ac,nc); if(i==m+1) continue; int nxt=fnd(1,n,dl[i]+1,dr[i]-1,root[i+1]); zp[nxt].push_back(i); updseg(1,n,dl[i]+1,dr[i]-1,ac-dp[i],1); } printf("%lld",dp[m+1]); }

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

constellation3.cpp: In function 'int main()':
constellation3.cpp:108:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<zf[i].size();j++) dl[zf[i][j]]=nmax(n+1-a[zf[i][j]].y);
               ~^~~~~~~~~~~~~
constellation3.cpp:113:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<zf[i].size();j++) dr[zf[i][j]]=nmin(n+1-a[zf[i][j]].y);
               ~^~~~~~~~~~~~~
constellation3.cpp:125:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<zp[i].size();j++) {nc+=dp[zp[i][j]]; ac+=dp[zp[i][j]];}
               ~^~~~~~~~~~~~~
constellation3.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
constellation3.cpp:99:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&h[i]);
                        ~~~~~^~~~~~~~~~~~
constellation3.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
constellation3.cpp:101:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].c);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...