#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#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};
}
if (a.f > b.f){
return a;
}
return 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){
// cout << "HEr\n";
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.f += 1;
c = max(c,{1,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.f += 1;
c = max(c,{1,1});
// cout << c.f << "," << c.s << " ";
upd(vals[i],c,0);
}
// cout << '\n';
curr = -1;
ll res = 0;
for (int i = 0; i < n; i++){
c = query(0,vals[i]-1,1);
c = max(c,{0,1});
c2 = query(vals[i],vals[i],0);
c2 = max(c2,{1,1});
// cout << c.f + c2.f << " ," << c.s*c2.s << " " << curr << '\n';
if (c.f+c2.f> curr){
curr = c.f+c2.f;
res = (c.s*c2.s)%mod;
} else if (c.f+c2.f == curr){
res = (res + c.s*c2.s) % mod;
}
}
// cout << res << '\n';
for (int i = 0; i < n-curr; i++){
res = (res*2) % mod;
}
// cout << res << '\n';
res = (res * 500000004) % mod;
cout << curr << " " << res << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
12988 KB |
Output isn't correct |
| 5 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
12892 KB |
Output isn't correct |
| 7 |
Correct |
4 ms |
12892 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
12892 KB |
Output isn't correct |
| 10 |
Correct |
3 ms |
12888 KB |
Output is correct |
| 11 |
Incorrect |
173 ms |
14664 KB |
Output isn't correct |
| 12 |
Incorrect |
168 ms |
14580 KB |
Output isn't correct |
| 13 |
Incorrect |
139 ms |
14324 KB |
Output isn't correct |
| 14 |
Incorrect |
183 ms |
14428 KB |
Output isn't correct |
| 15 |
Incorrect |
218 ms |
14800 KB |
Output isn't correct |
| 16 |
Incorrect |
257 ms |
15140 KB |
Output isn't correct |
| 17 |
Incorrect |
220 ms |
15328 KB |
Output isn't correct |
| 18 |
Incorrect |
264 ms |
15140 KB |
Output isn't correct |
| 19 |
Incorrect |
231 ms |
15440 KB |
Output isn't correct |
| 20 |
Incorrect |
219 ms |
15188 KB |
Output isn't correct |
