/*
-https://github.com/mostafa-saad/MyCompetitiveProgramming/blob/master/Olympiad/COCI/official/2017/contest3_solutions/solutions.pdf
*/
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
const int mod=1e9+7;
int add(int a,int b)
{
a+=b;
if(a>=mod)
a-=mod;
return a;
}
int multi(int a,int b)
{
ll t=(ll)a*b;
if(t>mod)
t%=mod;
return t;
}
const int N=2e5+5;
vector<int> duzina(N);
vector<int> start(N);
void update(int i,int d,int s)
{
for(;i<N;i+=i&(-i))
{
if(duzina[i]==d)
{
start[i]=add(start[i],s);
}
if(duzina[i]<d)
{
duzina[i]=d;
start[i]=s;
}
}
}
pair<int,int> get(int i)
{
int d=0;
int s=0;
for(;i;i-=i&(-i))
{
if(duzina[i]==d)
{
s=add(s,start[i]);
}
if(duzina[i]>d)
{
d=duzina[i];
s=start[i];
}
}
return make_pair(d,s);
}
vector<int> powers(N);
int main()
{
powers[0]=1;
for(int i=1;i<N;i++)
powers[i]=add(powers[i-1],powers[i-1]);
int n;
scanf("%i",&n);
vector<int> niz,niz1(n);
for(int i=0;i<n;i++)
scanf("%i",&niz1[i]);
vector<int> ss=niz1;
sort(all(ss));
ss.erase(unique(all(ss)),ss.end());
map<int,int> mapa;
for(int i=0;i<ss.size();i++)
mapa[ss[i]]=i+1;
for(int i=0;i<n;i++)
niz.pb(mapa[niz1[i]]);
reverse(all(niz));
vector<pair<int,int> > f,b; //f-decreasing, b-increasing
for(auto p:niz)
{
int best;
int num;
tie(best,num)=get(p);
if(best==0)
num=1;
best++;
f.pb({best,num});
update(p+1,best,num);
}
for(int i=0;i<N;i++)
duzina[i]=0,start[i]=0;
vector<int> rev;
for(auto p:niz)
{
rev.pb(N-p);
}
niz=rev;
for(auto p:niz)
{
int best;
int num;
tie(best,num)=get(p);
if(best==0)
num=1;
best++;
b.pb({best,num});
update(p+1,best,num);
}
int best=0;
int sum=0;
for(int i=0;i<n;i++)
{
int p=f[i].f+b[i].f-1;
int num=multi(powers[n-p],multi(f[i].s,b[i].s));
if(best==p)
sum=add(sum,num);
if(best<p)
{
best=p;
sum=num;
}
}
printf("%i %i\n",best,sum);
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:81:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ss.size();i++)
~^~~~~~~~~~
zoltan.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
zoltan.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&niz1[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2812 KB |
Output is correct |
| 9 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2684 KB |
Output is correct |
| 11 |
Correct |
142 ms |
17084 KB |
Output is correct |
| 12 |
Correct |
120 ms |
15412 KB |
Output is correct |
| 13 |
Correct |
111 ms |
13808 KB |
Output is correct |
| 14 |
Correct |
177 ms |
15588 KB |
Output is correct |
| 15 |
Correct |
229 ms |
18152 KB |
Output is correct |
| 16 |
Correct |
265 ms |
20212 KB |
Output is correct |
| 17 |
Correct |
187 ms |
18860 KB |
Output is correct |
| 18 |
Correct |
190 ms |
18868 KB |
Output is correct |
| 19 |
Correct |
180 ms |
18972 KB |
Output is correct |
| 20 |
Correct |
171 ms |
18920 KB |
Output is correct |
