#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
int n;
int a[200001];
map<int,int> mp;
map<int,int> nor;
int cntn=0;
void normalizare()
{
for(int i=1;i<=n;i++)
mp[a[i]]++;
int val;
for(auto it:mp)
{
val=it.first;
cntn++;
nor[val]=cntn;
}
for(int i=1;i<=n;i++)
a[i]=nor[a[i]];
}
struct node
{
int mxm[2];
int cnt[2];
};
node combine(node x, node y)
{
node rez;
for(int i=0;i<2;i++)
{
rez.mxm[i] = max(x.mxm[i],y.mxm[i]);
rez.cnt[i] = 0;
if(x.mxm[i]==rez.mxm[i])
rez.cnt[i] += x.cnt[i];
if(y.mxm[i]==rez.mxm[i])
rez.cnt[i] += y.cnt[i];
}
rez.cnt[0]%=MOD;
rez.cnt[1]%=MOD;
return rez;
}
node aint[810000];
node gol;
void upd(int nod, int st, int dr, int poz, node newval)
{
if(st==dr)
{
aint[nod]=newval;
return;
}
int mij=(st+dr)/2;
if(poz<=mij)
upd(nod*2,st,mij,poz,newval);
else
upd(nod*2+1,mij+1,dr,poz,newval);
aint[nod]=combine(aint[nod*2],aint[nod*2+1]);
}
node qry(int nod, int st, int dr, int le, int ri)
{
if(le>ri)
return gol;
if(le==st && ri==dr)
return aint[nod];
int mij=(st+dr)/2;
return combine(qry(nod*2,st,mij,le,min(mij,ri)),
qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
int put(int x, int exp)
{
if(exp==0) return 1;
if(exp%2==0) return put((x*x)%MOD, exp/2);
else return (put((x*x)%MOD, exp/2)*x)%MOD;
}
signed main()
{
gol.mxm[0]=0;
gol.mxm[1]=0;
gol.cnt[0]=0;
gol.cnt[1]=0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
normalizare();
node dp;
node x;
for(int i=1;i<=n;i++)
{
x = qry(1,1,cntn,a[i]+1,cntn);
dp.mxm[0] = x.mxm[0] + 1;
dp.cnt[0] = x.cnt[0];
if(dp.mxm[0]==1)
dp.cnt[0]=1;
x = qry(1,1,cntn,1,a[i]-1);
dp.mxm[1] = max(x.mxm[0], x.mxm[1]) + 1;
dp.cnt[1]=0;
if(x.mxm[0] + 1 == dp.mxm[1])
dp.cnt[1] += x.cnt[0];
if(x.mxm[1] + 1 == dp.mxm[1])
dp.cnt[1] += x.cnt[1];
if(dp.mxm[1]==1)
dp.cnt[1]=1;
dp.cnt[1]%=MOD;
dp.cnt[0]%=MOD;
upd(1,1,cntn,a[i],dp);
}
x = aint[1];
int maxim=0,cntm=0;
maxim=max(x.mxm[0],x.mxm[1]);
if(x.mxm[0]==maxim)
cntm+=x.cnt[0];
if(x.mxm[1]==maxim)
cntm+=x.cnt[1];
cout<<maxim<<" "<<(cntm*put(2,n-maxim))%MOD;
return 0;
}
/**
trebuie sa gasesc 2 secvente, una fiind crescatoare si cealalta descrescatoare
cea crescatoare incepe unde se termina cea descrescatoare
dp[i][0] = lungimea maxima a unei secvente descrescatoare care se termina pe pozitia i
dp[i][1] = lungimea maxima a 2 secvente, prima descrescatoare, a 2-a crescatoare, care se termina pe pozitia i
dp[i][0] = max(dp[j][0] + 1), unde a[j] > a[i]
dp[i][1] = max(max(dp[j][1] + 1 cu a[j] < a[i]), max(dp[j][0] + 1 cu a[j] < a[i]))
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
316 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
452 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
424 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 11 |
Runtime error |
403 ms |
39080 KB |
Memory limit exceeded |
| 12 |
Runtime error |
316 ms |
35896 KB |
Memory limit exceeded |
| 13 |
Incorrect |
293 ms |
26684 KB |
Output isn't correct |
| 14 |
Runtime error |
401 ms |
36372 KB |
Memory limit exceeded |
| 15 |
Runtime error |
568 ms |
41156 KB |
Memory limit exceeded |
| 16 |
Runtime error |
638 ms |
45024 KB |
Memory limit exceeded |
| 17 |
Runtime error |
457 ms |
40496 KB |
Memory limit exceeded |
| 18 |
Runtime error |
463 ms |
40488 KB |
Memory limit exceeded |
| 19 |
Runtime error |
451 ms |
40472 KB |
Memory limit exceeded |
| 20 |
Runtime error |
478 ms |
40480 KB |
Memory limit exceeded |
