Submission #743224

#	Time	Username	Problem	Language	Result	Execution time	Memory
743224		bgnbvnbv	Zoltan (COCI16_zoltan)	C++14	42 / 140	394 ms	23040 KiB

zoltan

#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=x1*x1%mod;
    if(y&1) x1=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;
        }
        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]);
        //cout << b[i]<<'\n';
    }
    ll ans=0;
    ll cur=0;
    for(int i=1;i<=2*n-1;i++)
    {
        cur=ans;
        if(dp[i][0]==mx)
        {
            ans+=cnt[i][0]*pw(2,n-mx-1)%mod;
        }
        if(dp[i][1]==mx)
        {
            ans+=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();
}

Compilation message (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:129:8: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  129 |     ll cur=0;
      |        ^~~

• Subtask 1: 42 / 140