| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 625321 |
2022-08-10T03:45:07 Z |
minhi1 |
Zoltan (COCI16_zoltan) |
C++14 |
|
233 ms |
16476 KB |
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define forn(i, a, b) for (int i = (a); i <= (b); ++i)
#define forb(i, b, a) for (int i = (b); i >= (a); --i)
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
template<class X, class Y> bool ckmax(X &x, Y y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template<class X, class Y> bool ckmin(X &x, Y y) {
if (x > y) {
x = y;
return true;
}
return false;
}
const int inf = (int)1e9 + 25;
const ll linf = 1e18;
const int N = 2e5 + 25;
/////////////////////////////////////////////////////
const int MOD = (int)1e9 + 7;
struct segmentTree {
int n;
vector<pair<int, int>> mx;
segmentTree(int _n = 0) {
n = _n;
mx.assign(4 * n + 6, {0, 0});
}
pair<int, int> comb(pair<int, int> x, pair<int, int> y) {
if (x.first > y.first) return x;
if (x.first < y.first) return y;
return {x.first, (x.second + y.second) % MOD};
}
void upd(int i, int l, int r, int p, pair<int, int> v) {
if (l > r) return;
if (l == r) {
mx[i] = comb(mx[i], v);
return;
}
int mid = (l + r) >> 1;
if (p <= mid) upd(i << 1, l, mid, p, v);
else upd(i << 1 | 1, mid + 1, r, p, v);
mx[i] = comb(mx[i << 1], mx[i << 1 | 1]);
}
void upd(int p, pair<int, int> v) {
upd(1, 1, n, p, v);
}
pair<int, int> get(int i, int l, int r, int u, int v) {
if (l > v || r < u || l > r || r < u) return {0, 0};
if (l >= u && r <= v) return mx[i];
int mid = (l + r) >> 1;
return comb(get(i << 1, l, mid, u, v), get(i << 1 | 1, mid + 1, r, u, v));
}
pair<int, int> get(int u, int v) {
return get(1, 1, n, u, v);
}
};
int n, a[N];
vector<int> values;
void compress() {
sort(values.begin(), values.end());
values.resize(unique(values.begin(), values.end()) - values.begin());
forn(i, 1, n) a[i] = lower_bound(values.begin(), values.end(), a[i]) - values.begin() + 1;
}
void sol() {
cin >> n;
forn(i, 1, n) cin >> a[i], values.pb(a[i]);
compress();
int m = values.size();
segmentTree inc(m), dec(m);
int res = 0, numInc, cntInc, numDec, cntDec;
ll tot = 0;
forb(i, n, 1) {
tie(numInc, cntInc) = inc.get(a[i] + 1, m);
if (++numInc == 1) cntInc = 1;
tie(numDec, cntDec) = dec.get(1, a[i] - 1);
if (++numDec == 1) cntDec = 1;
inc.upd(a[i], {numInc, cntInc}); dec.upd(a[i], {numDec, cntDec});
if (ckmax(res, numInc + numDec - 1)) {
tot = 1LL * cntInc * cntDec % MOD;
}
else if (numInc + numDec - 1 == res) {
tot = (tot + 1LL * cntInc * cntDec % MOD) % MOD;
}
}
forn(i, 1, n - res) tot = tot * 2LL % MOD;
cout << res << " " << tot;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
#ifdef DHT
freopen("voi.inp", "r", stdin);
#else
//freopen("triprime.inp", "r", stdin); freopen("triprime.out", "w", stdout);
#endif
int tt = 1;
// cin >> tt;
forn(i, 1, tt) sol();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
130 ms |
12808 KB |
Output is correct |
| 12 |
Correct |
112 ms |
11208 KB |
Output is correct |
| 13 |
Correct |
104 ms |
10556 KB |
Output is correct |
| 14 |
Correct |
141 ms |
11496 KB |
Output is correct |
| 15 |
Correct |
184 ms |
14180 KB |
Output is correct |
| 16 |
Correct |
233 ms |
16476 KB |
Output is correct |
| 17 |
Correct |
162 ms |
13640 KB |
Output is correct |
| 18 |
Correct |
177 ms |
13748 KB |
Output is correct |
| 19 |
Correct |
166 ms |
13780 KB |
Output is correct |
| 20 |
Correct |
164 ms |
13752 KB |
Output is correct |
