| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 313039 |
2020-10-15T02:58:51 Z |
Falcon |
Zoltan (COCI16_zoltan) |
C++17 |
|
404 ms |
10744 KB |
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.hpp"
#endif
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N) for(int i = 0; i < (N); ++i)
#define rrep(i, N) for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N) for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e) for(int i = (s); i <= (e); ++i)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back
#ifdef DEBUG
#define debug(x...) { ++dbg::depth; string dbg_vals = dbg::to_string(x); --dbg::depth; dbg::fprint(__func__, __LINE__, #x, dbg_vals); }
#define light_debug(x) { dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << " " << #x << " = " << x << endl; dbg::light = 0; }
#else
#define debug(x...) 42
#define light_debug(x) 42
#endif
template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }
template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
template<int mod>
class Modular {
int value;
public:
Modular(long long x = 0) { value = (int)((x % mod + mod) % mod); }
inline Modular& operator +=(Modular x) { value += x.value; if(value >= mod) value -= mod; return *this; }
inline Modular& operator -=(Modular x) { value -= x.value; if(value < 0) value += mod; return *this; }
inline Modular& operator *=(Modular x) { value = (int)((long long)x.value * value % mod); return *this; }
inline Modular& operator /=(Modular x) { *this *= x.pow(-1); } //TODO : Make this Extended Euclid to handle composite moduli.
inline Modular operator -() const { return Modular(-value); }
inline Modular& operator ++() { return *this += 1; }
inline Modular& operator --() { return *this -= 1; }
inline Modular operator ++(int) { Modular t = *this; *this += 1; return t; }
inline Modular operator --(int) { Modular t = *this; *this -= 1; return t; }
Modular pow(int n) const {
while(n < 0) n += mod - 1;
Modular v(1), a(value);
for(; n; a *= a, n >>= 1)
if(n & 1) v *= a;
return v;
}
inline Modular operator +(Modular x) const { return x += *this; }
inline Modular operator -(Modular x) const { return *this + (-x); }
inline Modular operator *(Modular x) const { return x *= *this; }
inline Modular operator /(Modular x) const { return (*this) * x.pow(-1); }
inline bool operator ==(Modular x) const { return value == x.value; }
inline bool operator !=(Modular x) const { return value != x.value; }
inline explicit operator int() const { return value; }
Modular fact() const {
Modular x(1);
for(int i = 1; i <= value; ++i) x *= i;
return x;
}
friend ostream& operator <<(ostream& os, Modular x) { return os << x.value; }
friend istream& operator >>(istream& is, Modular& x) { is >> x.value; x.value %= mod; return is; }
friend string to_string(Modular x) { return to_string(x.value); }
};
template<typename T, typename F = plus<T>>
class segtree {
int n;
T id;
F f;
vector<T> a;
public:
segtree(int n_, T id_ = T{}, F f_ = F{}) : n{n_}, id{id_}, f{f_}, a(n << 1, id) {}
segtree(const vector<T>& b, T id_ = T{}, F f_ = F{}) : segtree(b.size(), id_, f_) {
for(int i = 0; i < n; ++i)
a[i + n] = b[i];
for(int i = n - 1; i > 0; --i)
a[i] = a[i] = f(a[i << 1], a[i << 1 | 1]);
}
segtree(int n_, F f_) : segtree(n_, T{}, f_) {}
segtree(const vector<T>& b, F f_) : segtree(b, T{}, f_) {}
void update(int i, T t) {
for(i += n, a[i] = f(a[i], t), i >>= 1; i; i >>= 1)
a[i] = f(a[i << 1], a[i << 1 | 1]);
}
T query(int s, int e) {
T fr{id}, bk{id};
for(s += n, e += n; s < e; s >>= 1, e >>= 1) {
if(s & 1) fr = f(fr, a[s++]);
if(e & 1) bk = f(a[--e], bk);
}
return f(fr, bk);
}
};
constexpr int MOD{1'000'000'007};
void compress(vi& a) {
map<int, int> mp;
for(auto x : a) mp[x];
int i{};
traverse(mp, it) it->second = i++;
for(auto& x: a) x = mp[x];
}
vector<pair<int, Modular<MOD>>> LIS_starting_at(const vi& a) {
int n{static_cast<int>(a.size())};
int m{*max_element(all(a)) + 2};
auto combine = [](pair<int, Modular<MOD>> x, pair<int, Modular<MOD>> y) {
if(x.first < y.first) return y;
else if(x.first > y.first) return x;
else return x.second += y.second, x;
};
segtree<pair<int, Modular<MOD>>, decltype(combine)> seg(m, combine);
seg.update(m - 1, {0, 1});
vector<pair<int, Modular<MOD>>> res(n);
rep3(i, n - 1, 0, -1) {
res[i] = seg.query(a[i] + 1, m); ++res[i].first;
seg.update(a[i], res[i]);
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef DEBUG
freopen("debug", "w", stderr);
#endif
int n; cin >> n;
vi a(n); rep(i, n) cin >> a[i];
compress(a);
auto forward_lis = LIS_starting_at(a);
int m = *max_element(all(a));
for(auto& x : a) x = m - x;
auto backward_lis = LIS_starting_at(a);
int M{};
Modular<MOD> cnt{};
const Modular<MOD> TWO{2};
rep(i, n) {
m = forward_lis[i].first + backward_lis[i].first - 1;
if(m > M) cnt = 0, M = m;
else if(m < M) continue;
cnt += forward_lis[i].second * backward_lis[i].second * TWO.pow((n - 1) - (m - 1));
debug(M, cnt);
}
debug(a, forward_lis, backward_lis);
cout << M << ' ' << cnt << '\n';
#ifdef DEBUG
dbg::dout << "\nExecution time: " << clock() << "ms\n";
#endif
return 0;
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:26:29: warning: statement has no effect [-Wunused-value]
26 | #define debug(x...) 42
| ^~
zoltan.cpp:199:3: note: in expansion of macro 'debug'
199 | debug(M, cnt);
| ^~~~~
zoltan.cpp:26:29: warning: statement has no effect [-Wunused-value]
26 | #define debug(x...) 42
| ^~
zoltan.cpp:202:2: note: in expansion of macro 'debug'
202 | debug(a, forward_lis, backward_lis);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
512 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
181 ms |
8444 KB |
Output is correct |
| 12 |
Correct |
156 ms |
7544 KB |
Output is correct |
| 13 |
Correct |
145 ms |
7032 KB |
Output is correct |
| 14 |
Correct |
242 ms |
7416 KB |
Output is correct |
| 15 |
Correct |
322 ms |
9208 KB |
Output is correct |
| 16 |
Correct |
404 ms |
10744 KB |
Output is correct |
| 17 |
Correct |
208 ms |
9080 KB |
Output is correct |
| 18 |
Correct |
232 ms |
9080 KB |
Output is correct |
| 19 |
Correct |
207 ms |
9080 KB |
Output is correct |
| 20 |
Correct |
226 ms |
9080 KB |
Output is correct |
