#include <bits/stdc++.h>
#define N 200005
#define MOD 1000000007
using namespace std;
struct Node{
int val1,val2,occur1,occur2;
Node(){
val1 = 0,val2 = 0,occur1 = 0,occur2 = 0;
}
};
Node t[4*N];
Node cmp(Node a,Node b){
Node ret;
if(a.val1 == b.val1){
ret.val1 = a.val1;
ret.occur1 = (a.occur1 + b.occur1)%MOD;
}
else{
if(a.val1 > b.val1){
ret.val1 = a.val1;
ret.occur1 = a.occur1;
}
else{
ret.val1 = b.val1;
ret.occur1 = b.occur1;
}
}
if(a.val2 == b.val2){
ret.val2 = a.val2;
ret.occur2 = (a.occur2 + b.occur2)%MOD;
}
else{
if(a.val2 > b.val2){
ret.val2 = a.val2;
ret.occur2 = a.occur2;
}
else{
ret.val2 = b.val2;
ret.occur2 = b.occur2;
}
}
return ret;
}
int arr[N];
map<int,int> mp;
Node get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl){
return Node();
}
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl+tr)/2;
Node lc = get(v*2,tl,tm,l,r);
Node rc = get(v*2+1,tm+1,tr,l,r);
return cmp(lc,rc);
}
void upd(int v,int l,int r,int pos,Node val){
if(l == r){
t[v] = cmp(t[v],val);
return;
}
int m = (l+r)/2;
if(pos <= m)
upd(v*2,l,m,pos,val);
else upd(v*2+1,m+1,r,pos,val);
t[v] = cmp(t[v*2],t[v*2+1]);
}
int binpow(int a,int b){
int ret = 1;
while(b){
if(b&1){
ret = 1ll*ret*a%MOD;
}
a = 1ll*a *a%MOD;
b/=2;
}
return ret;
}
void solve(){
int n;
cin >> n;
for(int i=0;i<n;i++){
cin >> arr[i];
mp[arr[i]]=1;
}
int cnt = 1;
for(auto &u:mp){
u.second = cnt++;
}
int ans1 = 0,ans2=0;
int before = 0;
for(int i=n-1;i>=0;i--){
Node l = get(1,1,n,1,mp[arr[i]]-1);
Node r = get(1,1,n,mp[arr[i]]+1,n);
if(l.val1 == 0){
l.occur1 = 1;
}
if(r.val2 == 0){
r.occur2 = 1;
}
int ln = l.val1 + r.val2+1;
int occ = 1ll*l.occur1 * r.occur2%MOD * binpow(2,n-ln)%MOD;
if(ln == ans1){
ans2 = (ans2+occ)%MOD;
}
if(ln > ans1){
ans1 = ln;
ans2 = occ;
}
if(i == 0 && ln != ans1){
abort();
}
Node up;
up.val1 = l.val1 + 1;
up.occur1 = l.occur1;
up.val2 = r.val2 + 1;
up.occur2 = r.occur2;
upd(1,1,n,mp[arr[i]],up);
}
cout << ans1 << " " << ans2;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
Compilation message
zoltan.cpp: In function 'void solve()':
zoltan.cpp:92:9: warning: unused variable 'before' [-Wunused-variable]
92 | int before = 0;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
12908 KB |
Output is correct |
| 2 |
Correct |
10 ms |
12908 KB |
Output is correct |
| 3 |
Correct |
8 ms |
12908 KB |
Output is correct |
| 4 |
Correct |
9 ms |
12812 KB |
Output is correct |
| 5 |
Correct |
9 ms |
12908 KB |
Output is correct |
| 6 |
Correct |
8 ms |
12908 KB |
Output is correct |
| 7 |
Correct |
10 ms |
12908 KB |
Output is correct |
| 8 |
Correct |
9 ms |
12908 KB |
Output is correct |
| 9 |
Runtime error |
27 ms |
25964 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
27 ms |
25964 KB |
Execution killed with signal 6 |
| 11 |
Correct |
342 ms |
21100 KB |
Output is correct |
| 12 |
Correct |
280 ms |
19820 KB |
Output is correct |
| 13 |
Correct |
254 ms |
19564 KB |
Output is correct |
| 14 |
Runtime error |
390 ms |
40172 KB |
Execution killed with signal 6 |
| 15 |
Runtime error |
570 ms |
43628 KB |
Execution killed with signal 6 |
| 16 |
Runtime error |
637 ms |
46396 KB |
Execution killed with signal 6 |
| 17 |
Runtime error |
404 ms |
43372 KB |
Execution killed with signal 6 |
| 18 |
Runtime error |
387 ms |
43500 KB |
Execution killed with signal 6 |
| 19 |
Runtime error |
445 ms |
43372 KB |
Execution killed with signal 6 |
| 20 |
Runtime error |
381 ms |
43500 KB |
Execution killed with signal 6 |
