#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define mp make_pair
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
inline bool maximize(int &u, int v){
if(v > u){
u = v;
return true;
}
return false;
}
inline bool minimize(int &u, int v){
if(v < u){
u = v;
return true;
}
return false;
}
inline bool maximizell(long long &u, long long v){
if(v > u){
u = v;
return true;
}
return false;
}
inline bool minimizell(long long &u, long long v){
if(v < u){
u = v;
return true;
}
return false;
}
const int mod = 1e9 + 7;
inline int fastPow(int a, int n){
int res = 1;
while(n){
if(n & 1)res = 1ll * res * a * mod;
a = 1ll * a * a % mod;
n >>= 1;
}
return res;
}
inline void add(int &u, int v){
u += v;
if(u >= mod) u -= mod;
}
inline void sub(int &u, int v){
u -= v;
if(u < 0) u += mod;
}
const int maxN = 2e5 + 5;
const int inf = 2e9;
const long long infll = 1e18;
int n, a[maxN], comp[maxN];
namespace subtask1{
bool check(){
return n <= 20;
}
int C[21][21];
const int maxN = 21;
pair<int, int> fw[maxN];
pair<int, int> max(const pair<int, int> &a, const pair<int, int> &b){
if(a.first > b.first) return a;
if(b.first > a.first) return b;
int tmp = a.second;
add(tmp, b.second);
return mp(a.first, tmp);
}
void update(int x, pair<int,int> tmp){
for(; x <= n; x += x & -x)fw[x] = max(fw[x], tmp);
}
pair<int, int> get(int x){
pair<int, int> res = mp(0, 0);
for(; x >= 1; x &= x - 1)res = max(res, fw[x]);
return res;
}
#define left lep
#define right rai
int left[maxN], right[maxN];
int b[maxN];
int ansLen, ansCnt;
void solve(){
if(n == 1){
cout << 1 << ' ' << 1 << '\n';
return;
}
int ansLen = 0, mxLen = 0;
FOR(mask, 0, (1 << (n - 1)) - 1){
int cntL = 0, cntR = 0;
left[++cntL] = a[1];
FOR(i, 2, n){
if((mask >> (i - 2)) & 1){
left[++cntL] = a[i];
}else right[++cntR] = a[i];
}
int cnt = 0;
REP(i, cntL, 1)b[++cnt] = left[i];
FOR(i, 1, cntR)b[++cnt] = right[i];
FOR(i, 1, n)fw[i] = mp(0, 0);
FOR(i, 1, n){
pair<int, int> tmp = get(b[i] - 1);
if(tmp.first == 0)update(b[i], mp(1, 1));
else{
++tmp.first;
update(b[i], tmp);
}
}
pair<int, int> tmp = get(n);
if(maximize(ansLen, tmp.first))ansCnt = tmp.second;
else if(tmp.first == ansLen)add(ansCnt, tmp.second);
}
cout << ansLen << ' ' << ansCnt << "\n";
}
}
namespace ac{
struct Node{
int mxLen, cnt;
Node(){
mxLen = cnt = 0;
}
Node operator + (const Node &rhs) const {
if(mxLen > rhs.mxLen) return *this;
if(rhs.mxLen > mxLen) return rhs;
Node res = *this;
add(res.cnt, rhs.cnt);
return res;
}
};
Node inc[maxN], dec[maxN];
void updateInc(int x, Node val){
for(; x <= n; x += x & -x)inc[x] = inc[x] + val;
}
void updateDec(int x, Node val){
for(; x >= 1; x &= x - 1)dec[x] = dec[x] + val;
}
Node getInc(int x){
Node res;
for(; x >= 1; x &= x - 1)res = res + inc[x];
return res;
}
Node getDec(int x){
Node res;
for(; x <= n; x += x & -x)res = res + dec[x];
return res;
}
Node f[maxN], g[maxN];
void solve(){
FOR(i, 1, n){
Node tmp = getInc(a[i] - 1);
if(tmp.mxLen == 0){
f[i].mxLen = 1;
f[i].cnt = 1;
}
else{
f[i] = tmp;
f[i].mxLen++;
}
updateInc(a[i], f[i]);
}
FOR(i, 1, n){
Node tmp = getDec(a[i] + 1);
if(tmp.mxLen == 0){
g[i].mxLen = 1;
g[i].cnt = 1;
}
else{
g[i] = tmp;
g[i].mxLen++;
}
updateDec(a[i], g[i]);
}
Node res;
FOR(i, 1, n){
Node Merge;
Merge.mxLen = f[i].mxLen + g[i].mxLen - 1;
Merge.mxLen = 1ll * f[i].cnt * g[i].cnt % mod;
res = res + Merge;
}
cout << res.mxLen << ' ' << res.cnt;
}
}
void process(){
cin >> n;
FOR(i, 1, n){
cin >> a[i];
comp[i] = a[i];
}
sort(comp + 1, comp + 1 + n);
FOR(i, 1, n){
a[i] = lower_bound(comp + 1, comp + 1 + n, a[i]) - comp;
}
return ac :: solve();
}
/*
20
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 10485760
*/
#define NAME "subc"
int main(){
if(fopen(NAME".inp", "r")){
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t--)
process();
cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" ;
return 0;
}
Compilation message (stderr)
zoltan.cpp: In function 'int main()':
zoltan.cpp:209:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
209 | freopen(NAME".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:210:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
210 | freopen(NAME".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
