//#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
#defie 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 += inc[i].s*dc[i].s;
}else if (mxlen < cur){
mxlen = cur;
ans = inc[i].s*dc[i].s;
}
}
ans = (ans*pwr(2,n - mxlen))%mod;
cout<<ans;
}
Compilation message
zoltan.cpp:10:2: error: invalid preprocessing directive #defie; did you mean #define?
10 | #defie int long long
| ^~~~~
| define
zoltan.cpp: In function 'int main()':
zoltan.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i=1;i<d.size();i++){
| ~^~~~~~~~~
