#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
os << '{';
for(int i=0;i<sz(a);i++)
{
if(i>0&&i<sz(a))
os << ", ";
os << a[i];
}
os << '}';
return os;
}
const int N=2e5+5;
vector<int> duzina(N);
vector<vector<int> > start(N);
void add(int i,int d,vector<int> s)
{
//printf("Addujem %i %i\n",i,d);
//cout << s << endl;
for(;i<N;i+=i&(-i))
{
if(duzina[i]==d)
{
for(auto p:s)
start[i].pb(p);
}
if(duzina[i]<d)
{
duzina[i]=d;
start[i]=s;
}
}
}
pair<int,vector<int> > get(int i)
{
int d=0;
vector<int> s;
for(;i;i-=i&(-i))
{
if(duzina[i]==d)
{
for(auto p:start[i])
s.pb(p);
}
if(duzina[i]>d)
{
d=duzina[i];
s=start[i];
}
}
return make_pair(d,s);
}
void reset()
{
for(int i=0;i<N;i++)
{
duzina[i]=0;
start[i].clear();
}
}
const int mod=1e9+7;
int addd(int a,int b)
{
a+=b;
if(a>mod)
a-=mod;
return a;
}
int sub(int a,int b)
{
a-=b;
if(a<0)
a+=mod;
return a;
}
int multi(int a,int b)
{
return ((ll)a*b)%mod;
}
vector<int> powers(N);
int main()
{
powers[0]=1;
for(int i=1;i<N;i++)
powers[i]=addd(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;
for(int i=0;i<n;i++)
niz.pb(mapa[niz1[i]]);
deque<int> q;
q.pb(niz[0]);
int minn=niz[0],maxx=niz[0];
for(int i=1;i<n;i++)
{
if(niz[i]<minn)
{
minn=niz[i];
q.push_front(niz[i]);
continue;
}
if(niz[i]>maxx)
{
maxx=niz[i];
q.push_back(niz[i]);
continue;
}
reset();
int be=-1;
int sol=0;
int pos=0;
for(auto p:q)
{
int best;
vector<int> start;
tie(best,start)=get(p);
if(best==0)
{
assert(start.size()==0);
start.pb(pos);
}
best++;
add(p+1,best,start);
int adding=0;
for(auto p:start)
{
int delta=pos-p+1;
delta=n-delta-q.size();
adding=addd(adding,powers[delta]);
}
if(be==best)
sol=addd(sol,adding);
if(be<best)
{
be=best;
sol=adding;
}
pos++;
}
for(int j=i;j<n;j++)
{
int p=niz[j];
int best;
vector<int> start;
tie(best,start)=get(p);
if(best==0)
{
assert(start.size()==0);
start.pb(pos);
}
best++;
add(p+1,best,start);
int adding=0;
for(auto p:start)
{
int delta=pos-p+1;
delta=n-delta-q.size();
adding=addd(adding,powers[delta]);
}
if(be==best)
sol=addd(sol,adding);
if(be<best)
{
be=best;
sol=adding;
}
pos++;
}
reset();
pos=0;
for(int j=n-1;j>=i;j--)
{
int p=niz[j];
int best;
vector<int> start;
tie(best,start)=get(p);
if(best==0)
{
assert(start.size()==0);
start.pb(pos);
}
best++;
add(p+1,best,start);
int adding=0;
for(auto p:start)
{
int delta=pos-p+1;
delta=n-delta-q.size();
adding=addd(adding,powers[delta]);
}
if(be==best)
sol=addd(sol,adding);
if(be<best)
{
be=best;
sol=adding;
}
pos++;
}
for(auto p:q)
{
int best;
vector<int> start;
tie(best,start)=get(p);
if(best==0)
{
assert(start.size()==0);
start.pb(pos);
}
best++;
add(p+1,best,start);
int adding=0;
for(auto p:start)
{
int delta=pos-p+1;
delta=n-delta-q.size();
adding=addd(adding,powers[delta]);
}
if(be==best)
sol=addd(sol,adding);
if(be<best)
{
be=best;
sol=adding;
}
pos++;
}
printf("%i %i\n",be,sol);
return 0;
}
printf("%i %i\n",n,1);
return 0;
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:113:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ss.size();i++)
~^~~~~~~~~~
zoltan.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
zoltan.cpp:108: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 |
Runtime error |
13 ms |
13020 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Incorrect |
7 ms |
6648 KB |
Output isn't correct |
| 3 |
Incorrect |
7 ms |
6520 KB |
Output isn't correct |
| 4 |
Correct |
6 ms |
6648 KB |
Output is correct |
| 5 |
Correct |
6 ms |
6520 KB |
Output is correct |
| 6 |
Correct |
7 ms |
6648 KB |
Output is correct |
| 7 |
Runtime error |
52 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
46 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
48 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Incorrect |
60 ms |
29568 KB |
Output isn't correct |
| 11 |
Runtime error |
159 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
257 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
149 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
164 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
214 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
237 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 17 |
Incorrect |
326 ms |
22508 KB |
Output isn't correct |
| 18 |
Incorrect |
385 ms |
25356 KB |
Output isn't correct |
| 19 |
Incorrect |
333 ms |
23020 KB |
Output isn't correct |
| 20 |
Incorrect |
325 ms |
24740 KB |
Output isn't correct |
