#include <iostream>
#include <algorithm>
#include <cassert>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 2e5 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
constexpr int add(const int a,const int b){return a + b >= mod ? a + b - mod : a + b;}
constexpr int sub(const int a,const int b){return a >= b ? a - b : a - b + mod;}
constexpr int mul(const int a,const int b){return 1ll * a * b % mod;}
int n,val[maxn],lis_len[maxn],lis_count[maxn],lds_len[maxn],lds_count[maxn],t[maxn];
namespace fenwick{
constexpr int lowbit(const int x){return x & (-x);}
int f[maxn];
void modify(int pos,const int v){
for(;pos <= n + 1;pos += lowbit(pos))f[pos] = add(f[pos],v);
}
int query(int pos){
int res = 0;
for(;pos;pos -= lowbit(pos))res = add(res,f[pos]);
return res;
}
int query(const int l,const int r){return sub(query(r),query(l - 1));}
}
using pir = std::pair<int,int>;
std::vector<pir> vec[maxn];
void solve_lis(){
std::fill_n(t + 1,n,-inf);
lis_count[n + 1] = 1;
per(i,n,1){
let p = std::lower_bound(t + 1,t + n + 1,val[i],std::greater<int>()) - t;
lis_len[i] = p;
t[p] = val[i];
}
rep(i,1,n)vec[lis_len[i]].emplace_back(val[i],i);
vec[0].emplace_back(inf,n + 1);
rep(i,1,n)std::sort(vec[i].begin(),vec[i].end(),std::greater<pir>());
rep(i,1,n){
auto it = vec[i - 1].begin();
for(let &pir : vec[i]){
while(it != vec[i - 1].end() && it->first > pir.first){
fenwick::modify(it->second,lis_count[it->second]);
// debug("ins : %d\n",it->second);
it++;
}
// debug("ques : %d\n",pir.second);
lis_count[pir.second] = fenwick::query(pir.second + 1,n + 1);
}
for(auto p = vec[i - 1].begin();p != it;p++)fenwick::modify(p->second,sub(0,lis_count[p->second]));
}
// rep(i,1,n)debug("%d ",lis_len[i]);
// debug("\n");
// rep(i,1,n)debug("%d ",lis_count[i]);
// debug("\n");
}
void solve_lds(){
std::fill_n(t + 1,n,inf);
lds_count[n + 1] = 1;
per(i,n,1){
let p = std::lower_bound(t + 1,t + n + 1,val[i]) - t;
lds_len[i] = p;
t[p] = val[i];
}
rep(i,0,n)vec[i].clear();
rep(i,1,n)vec[lds_len[i]].emplace_back(val[i],i);
vec[0].emplace_back(-inf,n + 1);
rep(i,1,n)std::sort(vec[i].begin(),vec[i].end());
rep(i,1,n){
auto it = vec[i - 1].begin();
for(let &pir : vec[i]){
while(it != vec[i - 1].end() && it->first < pir.first){
fenwick::modify(it->second,lds_count[it->second]);
// debug("ins : %d\n",it->second);
it++;
}
// debug("ques : %d\n",pir.second);
lds_count[pir.second] = fenwick::query(pir.second + 1,n + 1);
}
for(auto p = vec[i - 1].begin();p != it;p++)fenwick::modify(p->second,sub(0,lds_count[p->second]));
}
// rep(i,1,n)debug("%d ",lds_len[i]);
// debug("\n");
// rep(i,1,n)debug("%d ",lds_count[i]);
// debug("\n");
}
int main(){
// #ifndef ONLINE_JUDGE
// std::freopen("fufu.in","r",stdin);
// #endif
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
rep(i,1,n)std::cin >> val[i];
solve_lis();
solve_lds();
int ans_len = 0,ans_count = 0;
rep(i,1,n)ans_len = std::max(ans_len,lis_len[i] + lds_len[i] - 1);
int pw = 1;
repn(n - ans_len)pw = add(pw,pw);
rep(i,1,n)
if(lis_len[i] + lds_len[i] - 1 == ans_len)
ans_count = add(ans_count,mul(pw,mul(lds_count[i],lis_count[i])));
std::cout << ans_len << " " << ans_count << "\n";
// rep(i,1,n)debug("%d ",lis_len[i]);
// debug("\n");
// rep(i,1,n)debug("%d ",lds_len[i]);
// debug("\n");
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
5084 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4944 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5028 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4944 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4944 KB |
Output is correct |
| 7 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5072 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5032 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5072 KB |
Output is correct |
| 11 |
Correct |
75 ms |
14800 KB |
Output is correct |
| 12 |
Correct |
63 ms |
13556 KB |
Output is correct |
| 13 |
Correct |
62 ms |
13120 KB |
Output is correct |
| 14 |
Correct |
71 ms |
11968 KB |
Output is correct |
| 15 |
Correct |
101 ms |
13724 KB |
Output is correct |
| 16 |
Correct |
97 ms |
15192 KB |
Output is correct |
| 17 |
Correct |
103 ms |
16644 KB |
Output is correct |
| 18 |
Correct |
114 ms |
16736 KB |
Output is correct |
| 19 |
Correct |
101 ms |
16552 KB |
Output is correct |
| 20 |
Correct |
119 ms |
16644 KB |
Output is correct |
