제출 #743247

#제출 시각아이디문제언어결과실행 시간메모리
743247bgnbvnbvZoltan (COCI16_zoltan)C++14
140 / 140
452 ms22328 KiB
#include<bits/stdc++.h> #define TASKNAME "codeforce" #define pb push_back #define pli pair<int,int> #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); using namespace std; using ll=int; const ll maxN=2e5+10; const ll inf=1e8; const ll mod=1e9+7; ll n,a[maxN],b[maxN*2],dp[maxN*2][2],cnt[maxN*2][2]; ll pw(ll x,ll y) { if(y==0) return 1; ll x1=pw(x,y/2); x1=1ll*x1*x1%mod; if(y&1) x1=1ll*x1*x%mod; return x1; } struct node { ll val,cnt; node() { val=-inf; cnt=0; } node operator+(const node&o) { node ans; if(val>o.val) ans.val=val,ans.cnt=cnt; else if(o.val>val) ans=o; else { ans.val=val; ans.cnt=cnt+o.cnt; if(ans.cnt>=mod) ans.cnt-=mod; } return ans; } }; struct IT { node st[4*maxN]; void update(ll pos,ll val1,ll val2,ll id=1,ll l=1,ll r=n) { if(l==r) { node cc; cc.val=val1; cc.cnt=val2; st[id]=st[id]+cc; return; } ll mid=l+r>>1; if(pos<=mid) update(pos,val1,val2,id*2,l,mid); else update(pos,val1,val2,id*2+1,mid+1,r); st[id]=st[id*2]+st[id*2+1]; } node get(ll i,ll j,ll id=1,ll l=1,ll r=n) { if(j<l||r<i) return node(); if(i<=l&&r<=j) return st[id]; ll mid=l+r>>1; return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r); } }t[2]; ll c[maxN]; void solve() { cin >> n; for(int i=1;i<=n;i++) cin >> a[i],c[i]=a[i]; sort(c+1,c+n+1); for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+n+1,a[i])-c; for(int i=1;i<=n;i++) b[i]=a[n-i+1]; for(int i=n;i<=2*n-1;i++) b[i]=a[i-n+1]; ll mx=0; for(int i=1;i<=2*n-1;i++) { dp[i][0]=1; cnt[i][0]=1; if(i==n) { dp[i][0]=-inf; cnt[i][0]=0; } else { node cc=t[0].get(1,b[i]-1); node vd; vd.val=dp[i][0]-1; vd.cnt=cnt[i][0]; cc=cc+vd; dp[i][0]=cc.val+1; cnt[i][0]=cc.cnt; } dp[i][1]=-inf; cnt[i][1]=0; if(i==n) { dp[i][1]=1; cnt[i][1]=1; node cc=t[0].get(1,b[i]-1); node vd; vd.val=dp[i][1]-1; vd.cnt=cnt[i][1]; cc=cc+vd; dp[i][1]=cc.val+1; cnt[i][1]=cc.cnt; } else { node cc=t[1].get(1,b[i]-1); node vd; vd.val=dp[i][1]-1; vd.cnt=cnt[i][1]; cc=cc+vd; dp[i][1]=cc.val+1; cnt[i][1]=cc.cnt; } cnt[i][0]%=mod; cnt[i][1]%=mod; mx=max({mx,dp[i][0],dp[i][1]}); t[0].update(b[i],dp[i][0],cnt[i][0]); t[1].update(b[i],dp[i][1],cnt[i][1]); } ll ans=0; ll cur=0; for(int i=1;i<=2*n-1;i++) { cur=ans; if(dp[i][0]==mx) { ans+=(long long)cnt[i][0]*pw(2,n-mx-1)%mod; //cout << cnt[i][0]<<'\n'; } if(dp[i][1]==mx) { //cout << cnt[i][1]<<'\n'; ans+=(long long)cnt[i][1]*pw(2,n-mx)%mod; } ans%=mod; } cout <<mx <<' '<<ans; } int main() { fastio //freopen(TASKNAME".INP","r",stdin); //freopen(TASKNAME".OUT","w",stdout); solve(); }

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

zoltan.cpp: In member function 'void IT::update(ll, ll, ll, ll, ll, ll)':
zoltan.cpp:57:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         ll mid=l+r>>1;
      |                ~^~
zoltan.cpp: In member function 'node IT::get(ll, ll, ll, ll, ll)':
zoltan.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         ll mid=l+r>>1;
      |                ~^~
zoltan.cpp: In function 'void solve()':
zoltan.cpp:130:8: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  130 |     ll cur=0;
      |        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...