# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
870123 | hqminhuwu | Zoltan (COCI16_zoltan) | C++14 | 3 ms | 10780 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>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <ll,ll>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
int i,n,a[N];
pii bit[N];
pll ans;
ll modpow (ll u, ll v){
if (v == 0)
return 1;
ll tmp = modpow(u,v / 2);
tmp = (tmp * tmp) % mod;
if (v & 1)
return (tmp * u) % mod;
return tmp;
}
void update1 (int u, pll len){
for (; u <= n; u += u & -u)
if (bit[u].st < len.st)
bit[u] = len;
else if (bit[u].st == len.st)
(bit[u].nd += len.nd) %= mod;
}
pll get1 (int u){
pll res = {0,1};
for (; u > 0; u -= u & -u)
if (res.st < bit[u].st)
res = bit[u];
else if (res.st == bit[u].st)
(res.nd += bit[u].nd) %= mod;
return res;
}
void update2 (int u, pll len){
for (; u > 0; u -= u & -u)
if (bit[u].st < len.st)
bit[u] = len;
else if (bit[u].st == len.st)
(bit[u].nd += len.nd) %= mod;
}
pll get2 (int u){
pll res = {0,1};
for (; u <= n; u += u & -u)
if (res.st < bit[u].st)
res = bit[u];
else if (res.st == bit[u].st)
(res.nd += bit[u].nd) %= mod;
return res;
}
void compr(){
vector <int> w;
forr (i,1,n)
w.pb(a[i]);
sort(all(w));
w.erase(unique(all(w)),w.end());
forr (i,1,n)
a[i] = lower_bound(all(w),a[i]) - w.begin() + 1;
}
pll p[N],s[N];
vector <int> v;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// #ifndef ONLINE_JUDGE
freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
// #endif
cin >> n;
forr (i,1,n)
cin >> a[i];
compr();
ford (i,n,1){
pii u = get1(a[i] - 1);
p[i] = {u.st + 1,u.nd};
update1(a[i],p[i]);
}
memset(bit,0,sizeof bit);
ford (i,n,1){
pii u = get2(a[i] + 1);
s[i] = {u.st + 1,u.nd};
update2(a[i],s[i]);
}
memset(bit,0,sizeof bit);
forr (i,1,n){
// cout << a[i] << " " << p[i].st << " " << p[i].nd << " " << s[i].st << " " << s[i].nd << "\n";
pll k = get1(a[i] - 1);
pll w = {k.st + s[i].st,(k.nd *s[i].nd) % mod};
if (w.st > ans.st)
ans = w;
else if (ans.st == w.st)
ans.nd = (ans.nd + w.nd) % mod;
// cout << i << " " << ans.st << " " << ans.nd << "\n";
// if (i == 1)
update1(a[i],p[i]);
}
cout << ans.st << " ";
// cout << 2 * modpow (2,mod - 2) << "\n";
cout << (ans.nd * modpow(2,n - ans.st)) % mod;
return 0;
}
/*
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |