#include <bits/stdc++.h>
using namespace std;
#define pii pair<ll,ll>
#define f first
#define s second
#define ll long long int
const int mxN = 2*1e5;
const ll mod = 1e9+7;
int n;
pii segtree[4*mxN+1];
pii segtree2[4*mxN+1];
pii comb(pii a, pii b){
if (a.f == b.f){
return {a.f,(a.s+b.s) % mod};
}
return max(a,b);
}
void upd(int t, pii v, bool w, int l = 0, int r = n-1, int idx = 0){
if (l > t || r < t){
return;
}
if (l == r){
if (w) segtree[idx] = comb(v,segtree[idx]);
else segtree2[idx] = comb(v,segtree2[idx]);
return;
}
int m = (l+r)/2;
upd(t,v,w,l,m,2*idx+1);
upd(t,v,w,m+1,r,2*idx+2);
if (w) segtree[idx] = comb(segtree[2*idx+1],segtree[2*idx+2]);
else segtree2[idx] = comb(segtree2[2*idx+1],segtree2[2*idx+2]);
return;
}
pii query(int tl, int tr, bool w, int l = 0, int r = n-1, int idx = 0){
if (tl > tr){
return {0,0};
}
if (l > tr || r < tl){
return {0,0};
}
if (l >= tl && r <= tr){
if (w) return segtree[idx];
return segtree2[idx];
}
int m = (l+r)/2;
return comb(query(tl,tr,w,l,m,2*idx+1),query(tl,tr,w,m+1,r,2*idx+2));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
vector<int> vals(n);
vector<pii> temp(n);
for (int i = 0; i < n; i++){
cin >> vals[i];
temp[i].f = vals[i];
temp[i].s = i;
}
sort(temp.begin(),temp.end());
int curr = -1;
int cnt = -1;
for (int i =0; i < n; i++){
if (temp[i].f != curr){
curr = temp[i].f;
cnt++;
}
vals[temp[i].s] = cnt;
}
for (int i =0; i < 4*mxN+1; i++) segtree[i] = {0,0};
pii c,c2;
for (int i = n - 1; i >= 0; i--){
c = query(0,vals[i]-1,1);
c = comb(c,{0,1});
c.f += 1;
// cout << c.f << ',' << c.s << " ";
upd(vals[i],c,1);
}
// cout << '\n';
for (int i =0; i < 4*mxN+1; i++) segtree2[i] = {0,0};
for (int i = n-1; i >= 0; i--){
c = query(vals[i]+1,n-1,0);
c = comb(c,{0,1});
c.f+=1;
// cout << c.f << "," << c.s << " ";
upd(vals[i],c,0);
}
// cout << '\n';
//
pii res = {1,n};
for (int i = 0; i < n; i++){
c = query(0,vals[i]-1,1);
c = comb(c,{0,1});
c2 = query(vals[i],vals[i],0);
c2 = comb(c2,{0,1});
// cout << c.f + c2.f << " ," << c.s*c2.s << "\n";
res = comb(res,{c.f+c2.f,(c.s*c2.s)%mod});
}
// cout << res.s << "\n";
for (int i = 0; i < n-res.f; i++){
res.s = (res.s*2) % mod;
}
// cout << res.s << '\n';
res.s = (res.s * 500000004) % mod;
cout << res.f << " " << res.s << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
25436 KB |
Output is correct |
| 2 |
Correct |
7 ms |
25296 KB |
Output is correct |
| 3 |
Correct |
6 ms |
25432 KB |
Output is correct |
| 4 |
Correct |
4 ms |
25436 KB |
Output is correct |
| 5 |
Correct |
4 ms |
25436 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
25436 KB |
Output isn't correct |
| 7 |
Correct |
6 ms |
25340 KB |
Output is correct |
| 8 |
Correct |
5 ms |
25436 KB |
Output is correct |
| 9 |
Correct |
6 ms |
25588 KB |
Output is correct |
| 10 |
Correct |
5 ms |
25432 KB |
Output is correct |
| 11 |
Correct |
190 ms |
29784 KB |
Output is correct |
| 12 |
Correct |
162 ms |
29236 KB |
Output is correct |
| 13 |
Correct |
159 ms |
29268 KB |
Output is correct |
| 14 |
Correct |
193 ms |
29524 KB |
Output is correct |
| 15 |
Correct |
292 ms |
30308 KB |
Output is correct |
| 16 |
Correct |
299 ms |
31312 KB |
Output is correct |
| 17 |
Incorrect |
232 ms |
30548 KB |
Output isn't correct |
| 18 |
Incorrect |
232 ms |
30676 KB |
Output isn't correct |
| 19 |
Incorrect |
231 ms |
30484 KB |
Output isn't correct |
| 20 |
Incorrect |
241 ms |
30668 KB |
Output isn't correct |
