#include <bits/stdc++.h>
using namespace std;
#define exetime cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
#define ynifnl(c) cout << ((c) ? "YES\n" : "NO\n")
#define ynif(c) cout << ((c) ? "YES" : "NO")
#define TASK "TEST"
#define lint long long int
#define ulint unsigned lint
#define sz(v) (int(v.size()))
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define fi first
#define se second
#define bit1(x) __builtin_popcountll(x)
#define coutf(f, d) cout << fixed << setprecision(d) << f
typedef pair <int, int> pii;
const int N = 2E5 + 25, MOD = 1E9 + 7;
int n, a[N], b[N];
pii R({0, 1}), G, lis[N], lds[N];
int mul (int a, int b) {
int T = 0;
for (; b; (a += a) %= MOD, b >>= 1) if (b & 1) (T += a) %= MOD;
return T;
}
int pw2 (int a) {
int T = 1;
for (; a; --a, (T *= 2) %= MOD);
return T;
}
void update_ (pii &A, pii B) {
if (A.fi < B.fi) A = B;
else if (A.fi == B.fi) (A.se += B.se) %= MOD;
}
namespace Fenwick_Tree {
pii BIT[2][N];
void update (bool t, int x, pii v) {
if (!t) for (; x <= n; update_(BIT[t][x], v), x += x & -x);
else for (; x; update_(BIT[t][x], v), x -= x & -x);
}
pii get (bool t, int x) {
pii g = {0, 1};
if (!t) for (; x; update_(g, BIT[t][x]), x -= x & -x);
else for (; x <= n; update_(g, BIT[t][x]), x += x & -x);
return g;
}
}
using namespace Fenwick_Tree;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
if (fopen(TASK".INP", "r")) {
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
for (int i = n; i; --i) {
lis[i] = get(1, a[i] + 1);
lds[i] = get(0, a[i] - 1);
lis[i].fi++;
lds[i].fi++;
G.fi = lis[i].fi + lds[i].fi - 1;
G.se = mul(lis[i].se, lds[i].se);
update_(R, G);
update(1, a[i], lis[i]); update(0, a[i], lds[i]);
}
cout << R.fi << " " << mul(pw2(n - R.fi), R.se);
return exetime, 0;
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | freopen(TASK".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4596 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
54 ms |
8476 KB |
Output is correct |
| 12 |
Correct |
50 ms |
7648 KB |
Output is correct |
| 13 |
Correct |
42 ms |
8016 KB |
Output is correct |
| 14 |
Correct |
71 ms |
8020 KB |
Output is correct |
| 15 |
Correct |
91 ms |
9080 KB |
Output is correct |
| 16 |
Correct |
111 ms |
10068 KB |
Output is correct |
| 17 |
Correct |
55 ms |
9344 KB |
Output is correct |
| 18 |
Correct |
56 ms |
9300 KB |
Output is correct |
| 19 |
Correct |
56 ms |
9296 KB |
Output is correct |
| 20 |
Correct |
55 ms |
9404 KB |
Output is correct |
