| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 743247 |
2023-05-17T09:10:22 Z |
bgnbvnbv |
Zoltan (COCI16_zoltan) |
C++14 |
|
452 ms |
22328 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=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();
}
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:130:8: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
130 | ll cur=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12868 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 4 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 5 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 6 |
Correct |
8 ms |
12792 KB |
Output is correct |
| 7 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 8 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 9 |
Correct |
10 ms |
12884 KB |
Output is correct |
| 10 |
Correct |
8 ms |
12924 KB |
Output is correct |
| 11 |
Correct |
270 ms |
20276 KB |
Output is correct |
| 12 |
Correct |
234 ms |
19264 KB |
Output is correct |
| 13 |
Correct |
198 ms |
18916 KB |
Output is correct |
| 14 |
Correct |
324 ms |
19236 KB |
Output is correct |
| 15 |
Correct |
381 ms |
20848 KB |
Output is correct |
| 16 |
Correct |
452 ms |
22120 KB |
Output is correct |
| 17 |
Correct |
321 ms |
22200 KB |
Output is correct |
| 18 |
Correct |
303 ms |
22204 KB |
Output is correct |
| 19 |
Correct |
298 ms |
22212 KB |
Output is correct |
| 20 |
Correct |
294 ms |
22328 KB |
Output is correct |
