#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
using namespace std;
const int N=2e5+5;
int n,m,T,k,arr[N];
pii t[N*4],dp1[N],dp2[N];
int power(int a, int b) {
int res=1;
while (b) {
if (b%2) {
res=(res*a)%MOD;
}
a=(a*a)%MOD; b/=2;
}
return res;
}
pii MAX(pii a, pii b) {
if (a.f!=b.f) return max(a,b);
return {a.f,a.s+b.s};
}
void build(int v, int tl, int tr) {
if (tl==tr) {
t[v]={0,0};
return;
}
int mid=(tl+tr)/2;
build(v*2,tl,mid); build(v*2+1,mid+1,tr);
t[v]=MAX(t[v*2],t[v*2+1]);
}
void update(int v, int tl, int tr, int ind, pii val) {
if (tl==tr) {
t[v]=MAX(t[v],val);
return;
}
int mid=(tl+tr)/2;
if (ind<=mid) update(v*2,tl,mid,ind,val);
else update(v*2+1,mid+1,tr,ind,val);
t[v]=MAX(t[v*2],t[v*2+1]);
}
pii query(int v, int tl, int tr, int l, int r) {
if (l>r) return {0,0};
if (tl==l && tr==r) return t[v];
int mid=(tl+tr)/2;
return MAX(query(v*2,tl,mid,l,min(mid,r)),query(v*2+1,mid+1,tr,max(l,mid+1),r));
}
void test_case() {
cin>>n;
int arr2[n+1]; map<int,int> IND;
for (int i=1; i<=n; i++) {
cin>>arr[i];
arr2[i]=arr[i];
}
sort(arr2+1,arr2+1+n);
for (int i=1; i<=n; i++) IND[arr2[i]]=i;
for (int i=1; i<=n; i++) arr[i]=IND[arr[i]];
build(1,1,n);
for (int i=n; i>=1; i--) {
pii val=query(1,1,n,arr[i]+1,n); if (val.f==0) val.s=1;
dp1[i]={val.f+1,val.s};
update(1,1,n,arr[i],dp1[i]);
}
build(1,1,n);
dp2[1]={1,1}; update(1,1,n,arr[1],dp2[1]);
for (int i=n; i>=1; i--) {
pii val=query(1,1,n,1,arr[i]-1); if (val.f==0) val.s=1;
dp2[i]={val.f+1,val.s};
update(1,1,n,arr[i],dp2[i]);
}
// dp1[1]={1,1}; update(1,1,n,arr[1],dp1[1]);
// for (int i=2; i<=n; i++) {
// pii val=query(1,1,n,1,arr[i]-1); if (val.f==0) val.s=1;
// dp1[i]={val.f+1,val.s};
// update(1,1,n,arr[i],dp1[i]);
// }
// build(1,1,n);
// dp2[1]={1,1}; update(1,1,n,arr[1],dp2[1]);
// for (int i=2; i<=n; i++) {
// pii val=query(1,1,n,arr[i]+1,n); if (val.f==0) val.s=1;
// dp2[i]={val.f+1,val.s};
// update(1,1,n,arr[i],dp2[i]);
// }
pii ans={0,0};
for (int i=1; i<=n; i++) {
pii val=query(1,1,n,1,arr[i]-1); if (val.f==0) val.s=1;
if (i==1) val={0,1};
pii ans2; ans2.f=val.f+dp1[i].f; ans2.s=val.s*dp1[i].s;
ans2.s*=power(2,n-ans2.f);
ans=MAX(ans,ans2);
// cout<<"I "<<i<<" "<<val.f<<" "<<val.s<<" "<<dp1[i].f<<" "<<dp1[i].s<<endl;
// cout<<ans2.f<<" "<<ans2.s<<endl;
}
cout<<ans.f<<" "<<ans.s<<endl;
}
main () {
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
T=1;
while (T--) test_case();
}
Compilation message
zoltan.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
1 | #pragma gcc diagnostic "-std=c++1z"
|
zoltan.cpp:114:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
114 | main () {
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
4444 KB |
Output isn't correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
4444 KB |
Output isn't correct |
| 6 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 11 |
Incorrect |
183 ms |
27256 KB |
Output isn't correct |
| 12 |
Incorrect |
156 ms |
25940 KB |
Output isn't correct |
| 13 |
Incorrect |
148 ms |
20816 KB |
Output isn't correct |
| 14 |
Incorrect |
193 ms |
25684 KB |
Output isn't correct |
| 15 |
Incorrect |
258 ms |
28268 KB |
Output isn't correct |
| 16 |
Incorrect |
298 ms |
30288 KB |
Output isn't correct |
| 17 |
Incorrect |
226 ms |
28404 KB |
Output isn't correct |
| 18 |
Incorrect |
231 ms |
28408 KB |
Output isn't correct |
| 19 |
Incorrect |
218 ms |
28496 KB |
Output isn't correct |
| 20 |
Incorrect |
223 ms |
28412 KB |
Output isn't correct |
