# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
140609 | Minnakhmetov | Zoltan (COCI16_zoltan) | C++14 | 339 ms | 9896 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const int MOD = 1e9 + 7;
struct Node {
int val, w;
};
Node operator + (Node a, Node b) {
if (a.val == b.val) {
if (a.val == 0)
return { 0, 1 };
Node c = { a.val, a.w + b.w };
if (c.w >= MOD)
c.w -= MOD;
return c;
}
if (a.val > b.val)
return a;
return b;
}
const int N = 2e5 + 5;
Node t[N * 4], mxr[N];
vector<int> vd;
int a[N];
int n;
void upd(int x, Node y, int v = 1, int L = 0, int R = vd.size() - 1) {
if (L == R) {
t[v] = t[v] + y;
}
else {
int m = (L + R) >> 1;
if (x <= m)
upd(x, y, v * 2, L, m);
else
upd(x, y, v * 2 + 1, m + 1, R);
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
Node que(int l, int r, int v = 1, int L = 0, int R = vd.size() - 1) {
if (l > r)
return { 0, 1 };
if (l == L && r == R) {
return t[v];
}
int m = (L + R) >> 1;
return que(l, min(m, r), v * 2, L, m) +
que(max(m + 1, l), r, v * 2 + 1, m + 1, R);
}
void brute() {
Node ans = { 0, 1 };
deque<int> q;
for (int i = 0; i < (1 << (n - 1)); i++) {
q = { a[0] };
for (int j = 1; j < n; j++) {
if ((i >> (j - 1)) & 1)
q.push_back(a[j]);
else
q.push_front(a[j]);
}
fill(t, t + vd.size() * 4, (Node){ 0, 1 });
Node cur = { 0, 1 };
for (int j = 0; j < n; j++) {
Node res = que(0, q[j] - 1);
res.val++;
upd(q[j], res);
ans = ans + res;
cur = cur + res;
}
}
cout << ans.val << " " << ans.w << "\n";
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
mt19937 rnd(time(0));
for (int i = 0; i < n; i++) {
cin >> a[i];
vd.push_back(a[i]);
}
sort(all(vd));
vd.erase(unique(all(vd)), vd.end());
for (int i = 0; i < n; i++) {
a[i] = lower_bound(all(vd), a[i]) - vd.begin();
}
fill(t, t + N * 4, (Node){ 0, 1 });
for (int i = n - 1; i >= 0; i--) {
Node res = que(a[i] + 1, vd.size() - 1);
res.val++;
upd(a[i], res);
mxr[i] = res;
}
fill(t, t + N * 4, (Node){ 0, 1 });
for (int i = n - 1; i > 0; i--) {
Node res = que(0, a[i] - 1);
res.val++;
upd(a[i], res);
}
Node mx_subseq = { 0, 1 }, mx_subseq_with_first = { 0, 0 };
for (int i = 0; i < n; i++) {
Node cur = que(0, a[i] - 1);
cur.val += mxr[i].val;
cur.w = cur.w * (ll)mxr[i].w % MOD;
// cout << "! " << cur.val << " " << cur.w << "\n";
// cout << "! " << mxr[i].val << " " << mxr[i].w << "\n";
if (i == 0)
mx_subseq_with_first = cur;
else
mx_subseq = mx_subseq + cur;
}
// cout << "!" << mx_subseq.val << " " << mx_subseq.w << "\n";
// cout << mx_subseq_with_first.val << " " << mx_subseq_with_first.w << "\n";
// for (int i = 0; i < n; i++) {
// cout << mxr[i].val << " " << mxr[i].w << "\n";
// }
// cout << "\n";
for (int i = 0; i < n - 1 - (mx_subseq.val > 1 ? mx_subseq.val : 0); i++) {
mx_subseq.w = mx_subseq.w * 2 % MOD;
}
for (int i = 0; i < n - mx_subseq_with_first.val; i++) {
mx_subseq_with_first.w = mx_subseq_with_first.w * 2 % MOD;
}
Node ans = mx_subseq + mx_subseq_with_first;
cout << ans.val << " " << ans.w;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |