oj.uz

Submission #743224

# Submission time Handle Problem Language Result Execution time Memory
743224 2023-05-17T08:58:03 Z bgnbvnbv Zoltan (COCI16_zoltan) C++14
42 / 140
 394 ms 23040 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 6 ms 12860 KB Output is correct
3 Correct 7 ms 12756 KB Output is correct
4 Correct 6 ms 12860 KB Output is correct
5 Correct 6 ms 12856 KB Output is correct
6 Correct 7 ms 12780 KB Output is correct
7 Incorrect 7 ms 12884 KB Output isn't correct
8 Incorrect 7 ms 12884 KB Output isn't correct
9 Incorrect 8 ms 12884 KB Output isn't correct
10 Incorrect 7 ms 12884 KB Output isn't correct
11 Incorrect 214 ms 21116 KB Output isn't correct
12 Incorrect 182 ms 19716 KB Output isn't correct
13 Incorrect 165 ms 19384 KB Output isn't correct
14 Incorrect 254 ms 20068 KB Output isn't correct
15 Incorrect 336 ms 21644 KB Output isn't correct
16 Incorrect 394 ms 22924 KB Output isn't correct
17 Incorrect 284 ms 22948 KB Output isn't correct
18 Incorrect 274 ms 23040 KB Output isn't correct
19 Incorrect 278 ms 22980 KB Output isn't correct
20 Incorrect 267 ms 22840 KB Output isn't correct