#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> ii;
#define LMAX 200005
const ll mod = 1000000007;
int n;
vector<ll> a;
int unum = 1;
void compress(){
map<int, int> comp;
for(int i = 0; i < a.size(); i++){
comp.insert({a[i], -1});
}
for(auto it = comp.begin(); it != comp.end(); it++){
it->second = unum++;
}
for(int i = 0; i < a.size(); i++){
a[i] = comp[a[i]];
}
}
ii merge(ii a, ii b){
if(a.first > b.first){
return a;
}else if(b.first > a.first){
return b;
}else{
a.second = (a.second + b.second)%mod;
return a;
}
}
ii t[4*LMAX];
void upd(int i, int s, int e, int indx, ii &val){
if(s == e){
t[i] = merge(t[i], val);
return;
}
int m = (s + e)>>1;
if(indx <= m){
upd(i*2, s, m, indx, val);
}else{
upd(i*2+1, m+1, e, indx, val);
}
t[i] = merge(t[i*2], t[i*2+1]);
}
ll POW(ll base, ll exp){
if(exp == 0) return 1;
if(exp == 1) return base;
ll temp = POW(base, exp/2);
temp = (temp*temp)%mod;
if(exp%2 == 0) return temp;
else return (base*temp)%mod;
}
ii query(int i, int s, int e, int l, int r){
if(s >= l && e <= r){
return t[i];
}
if(s > r || e < l) return {0, 0};
int m = (s + e)>>1;
return merge(query(i*2, s, m, l, r), query(i*2+1, m+1, e, l, r));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
a = vector<ll>(2*n-1);
for(int i = 0; i < n; i++){
ll t; cin>>t;
a[n+i-1] = t;
a[n-i-1] = t;
}
compress();
// for(int i = 0; i < a.size(); i++){
// cout<<a[i]<<" ";
// }
//cout<<endl;
for(int i = 0; i < 4*LMAX; i++){
t[i] = {0, 0};
}
for(int i = 0; i < a.size(); i++){
auto qval = query(1, 0, unum, 0, a[i]-1);
qval.first++;
qval = merge(qval, {1, 1});
upd(1, 0, unum, a[i], qval);
}
auto with_middle = query(1, 0, unum, 0, unum);
//cout<<"WITH_MIDDLE "<<with_middle.first<<" "<<with_middle.second<<endl;
for(int i = 0; i < 4*LMAX; i++){
t[i] = {0, 0};
}
for(int i = 0; i < a.size(); i++){
if(i == n-1) continue;
auto qval = query(1, 0, unum, 0, a[i]-1);
qval.first++;
qval = merge(qval, {1, 1});
upd(1, 0, unum, a[i], qval);
}
auto without_middle = query(1, 0, unum, 0, unum);
//cout<<"WITHOUT_MIDDLE "<<without_middle.first<<" "<<without_middle.second<<endl;
ll middle = 0;
if(with_middle.first > without_middle.first){
without_middle = {0, 0};
middle = with_middle.second;
}else if(without_middle.first == with_middle.first){
middle = (with_middle.second - without_middle.second + mod)%mod;
}
ll ans = (without_middle.second*POW(2, n-1-without_middle.first))%mod + (middle*POW(2, n-with_middle.first))%mod;
cout<<max(with_middle.first, without_middle.first)<<" "<<ans<<endl;
}
Compilation message
zoltan.cpp: In function 'void compress()':
zoltan.cpp:13:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a.size(); i++){
~~^~~~~~~~~~
zoltan.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a.size(); i++){
~~^~~~~~~~~~
zoltan.cpp: In function 'int main()':
zoltan.cpp:86:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a.size(); i++){
~~^~~~~~~~~~
zoltan.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a.size(); i++){
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
12792 KB |
Output is correct |
| 2 |
Correct |
16 ms |
12904 KB |
Output is correct |
| 3 |
Correct |
12 ms |
12972 KB |
Output is correct |
| 4 |
Correct |
12 ms |
13052 KB |
Output is correct |
| 5 |
Correct |
13 ms |
13052 KB |
Output is correct |
| 6 |
Correct |
13 ms |
13052 KB |
Output is correct |
| 7 |
Correct |
17 ms |
13088 KB |
Output is correct |
| 8 |
Incorrect |
14 ms |
13088 KB |
Output isn't correct |
| 9 |
Correct |
15 ms |
13088 KB |
Output is correct |
| 10 |
Correct |
15 ms |
13088 KB |
Output is correct |
| 11 |
Correct |
473 ms |
23088 KB |
Output is correct |
| 12 |
Correct |
478 ms |
23088 KB |
Output is correct |
| 13 |
Correct |
424 ms |
23088 KB |
Output is correct |
| 14 |
Correct |
586 ms |
23088 KB |
Output is correct |
| 15 |
Correct |
785 ms |
23888 KB |
Output is correct |
| 16 |
Execution timed out |
1087 ms |
25552 KB |
Time limit exceeded |
| 17 |
Correct |
700 ms |
25552 KB |
Output is correct |
| 18 |
Correct |
668 ms |
25552 KB |
Output is correct |
| 19 |
Correct |
728 ms |
25552 KB |
Output is correct |
| 20 |
Correct |
779 ms |
25552 KB |
Output is correct |
