#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;
int n;
pii decr[mxN];
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 < n; i++) decr[i] = {1,1};
for (int i =0; i < 4*mxN+1; i++) segtree[i] = {0,0};
// upd(0,{0,1},1);
pii c,c2;
for (int i = n - 1; i >= 0; i--){
// cout << vals[i]-1 << " ";
c = query(0,vals[i]-1,1);
c.f += 1;
decr[i] = max(decr[i],c);
// decr[i].f += 1;
/* if (decr[i].f == 1){
decr[i].s += 1;
}*/
upd(vals[i],decr[i],1);
}
for (int i =0; i < 4*mxN+1; i++) segtree2[i] = {0,0};
// upd(0,{0,1},0);
/* for (int i =0; i < n; i++) cout << decr[i].f << ',' << decr[i].s << " ";
cout << '\n';
for (int i =0; i < n; i++) cout << vals[i] << " ";
cout << '\n';*/
curr = -1;
cnt = 0;
for (int i =0; i < n; i++){
c = query(0,vals[i]-1,0);
c.f += 1;
c2 = query(0,vals[i]-1,1);
c2.f += 1;
// if (c2.f == 1) c2.s += 1;
/*if (c.f < c2.f){
swap(c,c2);
}
if (c2.f == c.f){
c.s += c2.s;
}*/
c = comb(c,c2);
c = max(c,{1,1});
if (c.f > curr){
curr = c.f;
cnt = c.s;
} else if (c.f == curr){
cnt += c.s;
}
//cout << c.f << "," << c.s << " ";
upd(vals[i],c,0);
}
// cout << '\n';
ll mod = 1e9+7;
ll res = cnt;
for (int i = 0; i < n-curr; i++){
res = (res*2) % mod;
}
res = (res * 500000004) % mod;
cout << curr << " " << res << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12888 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 |
12892 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 |
4 ms |
12892 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
12892 KB |
Output isn't correct |
| 10 |
Correct |
4 ms |
12892 KB |
Output is correct |
| 11 |
Incorrect |
163 ms |
16992 KB |
Output isn't correct |
| 12 |
Incorrect |
131 ms |
16240 KB |
Output isn't correct |
| 13 |
Incorrect |
126 ms |
16048 KB |
Output isn't correct |
| 14 |
Incorrect |
165 ms |
16692 KB |
Output isn't correct |
| 15 |
Incorrect |
194 ms |
17116 KB |
Output isn't correct |
| 16 |
Incorrect |
225 ms |
18004 KB |
Output isn't correct |
| 17 |
Correct |
195 ms |
17656 KB |
Output is correct |
| 18 |
Correct |
206 ms |
17728 KB |
Output is correct |
| 19 |
Correct |
196 ms |
17488 KB |
Output is correct |
| 20 |
Correct |
208 ms |
17440 KB |
Output is correct |
