//#include <iostream>
//#include <vector>
//#include <algorithm>
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define left (h<<1),l,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define int long long
using namespace std;
const int N = 200005,mx = 200005,mod=1000000007;
int a[N];
pair <int,int> inc[N],t[4*N],dc[N];
vector <pair<int,int>> d;
void upd(int h,int l,int r,int idx,int val1,int val2){
if (l == r){
t[h].f=val1;
t[h].s+=val2;
return;
}
if (idx > (l+r)>>1) upd(right,idx,val1,val2);
else upd(left,idx,val1,val2);
if (t[h*2].f == t[h*2 + 1].f) t[h] = {t[h*2].f,t[h*2+1].s + t[h*2].s};
else if(t[h*2].f > t[h*2 + 1].f) t[h] = t[h*2];
else t[h] = t[h*2 + 1];
}
pair<int,int> get(int h,int l,int r,int L,int R){
if (r < L || R < l) return {0,0};
if (L <= l && r <= R) return t[h];
pair <int,int> x = get(left,L,R),y = get(right,L,R);
if (x.f == y.f) return {x.f,x.s+y.s};
else if(x.f > y.f) return x;
return y;
}
void build(int h,int l,int r){
if (l==r){
t[h] = {0,0};
return;
}
build(left),build(right);
t[h] = {0,0};
}
int pwr(int a,int b){
int res=1;
while(b){
if (b%2) res=(res*a)%mod;
a=(a*a)%mod;
b/=2;
}
return res;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n;
cin>>n;
for(int i =1; i<=n;i++){
cin>>a[i];
d.pb({a[i],i});
}
sort(d.begin(),d.end());
a[d[0].s] = 1;
for (int i=1;i<d.size();i++){
a[d[i].s] = a[d[i - 1].s];
if (d[i].f > d[i - 1].f) a[d[i].s]++;
}
//increasing
for (int i = n; i >= 1; i--){
pair <int,int> g = get(1,1,mx,a[i] + 1,mx);
inc[i] = {g.f + 1,g.s};
if (g.f > 0){
upd(1,1,mx,a[i],g.f+1,g.s);
}else{
inc[i].s = 1;
upd(1,1,mx,a[i],1,1);
}
}
build(1,1,mx);
//decreasing
for (int i = n; i >= 1; i--){
pair <int,int> g = get(1,1,mx,1,a[i] - 1);
dc[i] = {g.f + 1,g.s};
if (g.f > 0){
upd(1,1,mx,a[i],g.f+1,g.s);
}else{
dc[i].s = 1;
upd(1,1,mx,a[i],1,1);
}
}
int mxlen = 0,ans = 0;
for (int i = 1; i <= n; i++){
int cur = inc[i].f + dc[i].f - 1;
if (mxlen == cur){
ans = (ans + inc[i].s*dc[i].s)%mod;
}else if (mxlen < cur){
mxlen = cur;
ans = (inc[i].s*dc[i].s)%mod;
}
}
ans = (ans*pwr(2,n - mxlen))%mod;
cout<<ans;
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:70:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i=1;i<d.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
8556 KB |
Output isn't correct |
| 2 |
Incorrect |
6 ms |
8516 KB |
Output isn't correct |
| 3 |
Incorrect |
7 ms |
8520 KB |
Output isn't correct |
| 4 |
Incorrect |
6 ms |
8532 KB |
Output isn't correct |
| 5 |
Incorrect |
6 ms |
8540 KB |
Output isn't correct |
| 6 |
Incorrect |
8 ms |
8480 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
8584 KB |
Output isn't correct |
| 8 |
Incorrect |
7 ms |
8528 KB |
Output isn't correct |
| 9 |
Incorrect |
8 ms |
8532 KB |
Output isn't correct |
| 10 |
Incorrect |
6 ms |
8532 KB |
Output isn't correct |
| 11 |
Incorrect |
130 ms |
17596 KB |
Output isn't correct |
| 12 |
Incorrect |
136 ms |
16320 KB |
Output isn't correct |
| 13 |
Incorrect |
121 ms |
15792 KB |
Output isn't correct |
| 14 |
Incorrect |
150 ms |
16436 KB |
Output isn't correct |
| 15 |
Incorrect |
205 ms |
18316 KB |
Output isn't correct |
| 16 |
Incorrect |
238 ms |
19704 KB |
Output isn't correct |
| 17 |
Incorrect |
158 ms |
19852 KB |
Output isn't correct |
| 18 |
Incorrect |
150 ms |
19844 KB |
Output isn't correct |
| 19 |
Incorrect |
160 ms |
19828 KB |
Output isn't correct |
| 20 |
Incorrect |
175 ms |
19876 KB |
Output isn't correct |
