| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 676162 |
2022-12-29T15:20:49 Z |
alexdd |
Zoltan (COCI16_zoltan) |
C++17 |
|
475 ms |
29120 KB |
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll 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]];
}
ll put(ll x, ll 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;
}
pair<int,int> aint[810000];
pair<int,int> combine(pair<int,int> x, pair<int,int> y)
{
pair<int,int> aux;
aux.first = max(x.first, y.first);
int auxx=0;
if(aux.first == x.first)
auxx += x.second;
auxx%=MOD;
if(aux.first == y.first)
auxx += y.second;
auxx%=MOD;
aux.second = auxx;
return aux;
}
void reset_aint()
{
for(int i=0;i<810000;i++)
aint[i]={0,0};
}
void upd(int nod, int st, int dr, int poz, pair<int,int> newval)
{
if(st==dr)
{
aint[nod]=combine(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]);
}
pair<int,int> qry(int nod, int st, int dr, int le, int ri)
{
if(le>ri)
return {0,0};
if(le==st && dr==ri)
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));
}
pair<int,int> dp1[200001];
pair<int,int> dp2[200001];
void calc_dp1()
{
reset_aint();
for(int i=1;i<=cntn;i++)
dp1[i]=dp2[i]={0,0};
pair<int,int> x;
for(int i=n;i>0;i--)
{
x = qry(1,1,cntn,a[i]+1,cntn);
x.first = x.first + 1;
if(x.first == 1)
x.second = 1;
upd(1,1,cntn,a[i],x);
dp1[a[i]] = combine(dp1[a[i]], x);
}
}
void calc_dp2()
{
reset_aint();
pair<int,int> x;
for(int i=n;i>0;i--)
{
x = qry(1,1,cntn,1,a[i]-1);
x.first = x.first + 1;
if(x.first == 1)
x.second = 1;
upd(1,1,cntn,a[i],x);
dp2[a[i]] = combine(dp2[a[i]], x);
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
normalizare();
calc_dp1();
calc_dp2();
pair<int,int> rez = {0,0};
pair<int,int> x ;
for(int i=1;i<=cntn;i++)
{
//cout<<i<<" "<<dp1[i].first<<" "<<dp2[i].first<<"\n";
x.first = dp1[i].first + dp2[i].first - 1;
x.second = (1LL*dp1[i].second * dp2[i].second)%MOD;
rez = combine(rez, x);
}
if(rez.first == 1)
{
cout<<1<<" ";
cout<<(put(2,n-1) * n) % MOD;
return 0;
}
cout<<rez.first<<" "<<(rez.second * put(2, n-rez.first))%MOD;
//cout<<rez.first<<" "<<rez.second;
return 0;
}
/**
input:
20
13 6 5 15 19 18 9 4 14 17 7 10 3 1 2 8 20 16 11 12
13 6 5 4 3 1 2 8 11 12
correct output:
9 32768
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6592 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6612 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6612 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6740 KB |
Output is correct |
| 8 |
Correct |
5 ms |
6740 KB |
Output is correct |
| 9 |
Correct |
5 ms |
6740 KB |
Output is correct |
| 10 |
Correct |
4 ms |
6740 KB |
Output is correct |
| 11 |
Correct |
299 ms |
24552 KB |
Output is correct |
| 12 |
Correct |
240 ms |
22196 KB |
Output is correct |
| 13 |
Correct |
221 ms |
21192 KB |
Output is correct |
| 14 |
Correct |
302 ms |
22168 KB |
Output is correct |
| 15 |
Correct |
390 ms |
26060 KB |
Output is correct |
| 16 |
Correct |
475 ms |
29120 KB |
Output is correct |
| 17 |
Correct |
328 ms |
25732 KB |
Output is correct |
| 18 |
Incorrect |
321 ms |
25728 KB |
Output isn't correct |
| 19 |
Correct |
331 ms |
25852 KB |
Output is correct |
| 20 |
Incorrect |
319 ms |
25736 KB |
Output isn't correct |
