#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 power[maxN], n, a[maxN], comp[maxN];
struct Node{
int len, cnt;
Node(int lenVal = 0, int cntVal = 0){
len = lenVal;
cnt = cntVal;
}
Node operator + (const Node &rhs) const {
if(len > rhs.len) return *this;
if(rhs.len > len) return rhs;
Node res = *this;
add(res.cnt, rhs.cnt);
return res;
}
};
Node f[maxN], g[maxN];
#define dec DECCCCC
Node inc[maxN], dec[maxN];
void updateInc(int x, Node val){
for(; x <= n; x += x & -x)inc[x] = inc[x] + val;
}
Node getInc(int x){
Node res;
for(; x >= 1; x &= x - 1)res = res + inc[x];
return res;
}
void updateDec(int x, Node val){
for(; x >= 1; x &= x - 1)dec[x] = dec[x] + val;
}
Node getDec(int x){
Node res;
for(; x <= n; x += x & -x)res = res + dec[x];
return res;
}
void process(){
cin >> n;
power[0] = 1;
FOR(i, 1, n){
cin >> a[i];
power[i] = 2ll * power[i - 1] % mod;
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;
}
REP(i, n, 1){
Node val = getInc(a[i] - 1);
if(val.len == 0)f[i] = Node(1, 1);
else f[i] = val, ++f[i].len;
updateInc(a[i], f[i]);
val = getDec(a[i] + 1);
if(val.len == 0)g[i] = Node(1, 1);
else g[i] = val, ++g[i].len;
updateDec(a[i], g[i]);
}
Node res;
FOR(i, 1, n){
Node Merge;
Merge.len = f[i].len + g[i].len - 1;
Merge.cnt = 1ll * f[i].cnt * g[i].cnt % mod * power[n - Merge.len] % mod;
res = res + Merge;
}
cout << res.len << ' ' << res.cnt;
}
#define NAME "Zoltan"
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;
}
컴파일 시 표준 에러 (stderr) 메시지
zoltan.cpp: In function 'int main()':
zoltan.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | freopen(NAME".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
128 | freopen(NAME".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |