#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] = v;
else segtree2[idx] = v;
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 (l > r){
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] = {0,0};
for (int i =0; i < 4*mxN+1; i++) segtree[i] = {0,0};
for (int i = n - 1; i >= 0; i--){
decr[i] = query(0,vals[i]-1,1);
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};
/* 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;
pii c,c2;
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;
c = max(c,c2);
/*if (c2.f == c.f){
c.s += c2.s;
}*/
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;
}
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 |
12888 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
12892 KB |
Output isn't correct |
| 8 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
12892 KB |
Output isn't correct |
| 10 |
Correct |
4 ms |
12892 KB |
Output is correct |
| 11 |
Incorrect |
143 ms |
17116 KB |
Output isn't correct |
| 12 |
Incorrect |
124 ms |
16468 KB |
Output isn't correct |
| 13 |
Incorrect |
117 ms |
16500 KB |
Output isn't correct |
| 14 |
Incorrect |
180 ms |
16988 KB |
Output isn't correct |
| 15 |
Incorrect |
191 ms |
17748 KB |
Output isn't correct |
| 16 |
Incorrect |
224 ms |
18584 KB |
Output isn't correct |
| 17 |
Incorrect |
184 ms |
18516 KB |
Output isn't correct |
| 18 |
Incorrect |
184 ms |
17968 KB |
Output isn't correct |
| 19 |
Incorrect |
188 ms |
18000 KB |
Output isn't correct |
| 20 |
Incorrect |
189 ms |
18036 KB |
Output isn't correct |
