#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<__int128,__int128>
#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);
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]);
}
pair<int,int> ans={0,0};
build(1,1,n);
for (int i=2; i<=n; i++) {
pii val=query(1,1,n,1,arr[i]-1); if (val.f==0) val.s=1;
pii ans2; ans2.f=val.f+dp1[i].f; ans2.s=((val.s%MOD)*(dp1[i].s%MOD))%MOD;
ans2.s*=power(2,n-ans2.f); ans2.s%=MOD;
ans=MAX(ans,ans2);
// cout<<"I "<<i<<" "<<val.f<<" "<<val.s<<" "<<dp1[i].f<<" "<<dp1[i].s<<endl;
// cout<<ans2.f<<" "<<ans2.s<<endl;
update(1,1,n,arr[i],dp2[i]);
}
pii mx1={0,1},mx2={0,1};
for (int i=2; i<=n; i++) {
if (arr[i]<arr[1]) mx2=MAX(mx2,dp2[i]);
else if (arr[i]>arr[1]) mx1=MAX(mx1,dp1[i]);
}
pair<int,int> val={mx1.f+mx2.f+1,((mx1.s%MOD)*(mx2.s%MOD))%MOD}; val.s*=power(2,n-val.f); val.s%=MOD;
ans.s%=MOD; ans=MAX(ans,val);
// for (int i=1; i<=n; i++) cout<<arr[i]<<" "; cout<<endl;
// cout<<val.f<<" "<<val.s<<endl;
cout<<ans.f<<" "<<ans.s%MOD<<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:110:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
110 | main () {
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6696 KB |
Output is correct |
| 9 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 11 |
Runtime error |
386 ms |
44452 KB |
Memory limit exceeded |
| 12 |
Runtime error |
314 ms |
42892 KB |
Memory limit exceeded |
| 13 |
Correct |
305 ms |
32156 KB |
Output is correct |
| 14 |
Runtime error |
334 ms |
43092 KB |
Memory limit exceeded |
| 15 |
Runtime error |
501 ms |
45360 KB |
Memory limit exceeded |
| 16 |
Runtime error |
465 ms |
47184 KB |
Memory limit exceeded |
| 17 |
Runtime error |
461 ms |
45392 KB |
Memory limit exceeded |
| 18 |
Runtime error |
465 ms |
45396 KB |
Memory limit exceeded |
| 19 |
Runtime error |
451 ms |
45292 KB |
Memory limit exceeded |
| 20 |
Runtime error |
474 ms |
45340 KB |
Memory limit exceeded |
