| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 736167 | marvinthang | Zoltan (COCI16_zoltan) | C++17 | 132 ms | 6124 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.
/*************************************
* author: marvinthang *
* created: 05.08.2022 10:17:30 *
*************************************/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define div ___div
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define FULL(i) (MASK(i) - 1)
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T> print_op(vector <T>) { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V> scan_op(pair <U, V>) { return in >> u.fi >> u.se; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.fi << ", " << u.se << ')'; }
template <class InIter, class OutIter> void compress(InIter first, InIter last, OutIter result) { vector <__typeof(*first)> v(first, last); sort(v.begin(), v.end()); unique(v.begin(), v.end()); while (first != last) { *result = lower_bound(v.begin(), v.end(), *first) - v.begin() + 1; ++first; ++result; } }
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
const int MAX = 2e5 + 5;
const int MOD = 1e9 + 7;
namespace Mod {
inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
#ifdef __GNUC__
asm(
"divl %4 \n\t"
: "=a" (d), "=d" (m)
: "d" (xh), "a" (xl), "r" (y)
);
#else
__asm {
mov edx, dword ptr[xh];
mov eax, dword ptr[xl];
div dword ptr[y];
mov dword ptr[d], eax;
mov dword ptr[m], edx;
};
#endif
out_d = d; out_m = m;
}
template <int MOD>
struct ModInt {
unsigned int val;
ModInt(void): val(0) {}
ModInt(const long long &x) { *this = x; }
ModInt & normalize(const unsigned int &v) {
val = v >= MOD ? v - MOD : v;
return *this;
}
bool operator ! (void) { return !val; }
ModInt & operator = (const ModInt &x) { val = x.val; return *this; }
ModInt & operator = (const long long &x) { return normalize(x % MOD + MOD); }
ModInt operator - (void) { return ModInt(MOD - val); }
ModInt & operator += (const ModInt &other) { return normalize(val + other.val); }
ModInt & operator -= (const ModInt &other) { return normalize(val + MOD - other.val); }
ModInt & operator /= (const ModInt &other) { return *this *= other.inv(); }
ModInt & operator *= (const ModInt &other) {
unsigned dummy;
fasterLLDivMod((unsigned long long) val * other.val, MOD, dummy, val);
return *this;
}
ModInt operator + (const ModInt &other) const { return ModInt(*this) += other; }
ModInt operator - (const ModInt &other) const { return ModInt(*this) -= other; }
ModInt operator * (const ModInt &other) const { return ModInt(*this) *= other; }
ModInt operator / (const ModInt &other) const { return ModInt(*this) /= other; }
ModInt pow(const ModInt &Exp) const {
int n = Exp.val;
assert(n >= 0);
ModInt res = 1, a = *this;
while (n) {
if (n & 1) res = res * a;
a = a * a;
n >>= 1;
}
return res;
}
ModInt pow(long long Exp) const {
assert(Exp >= 0);
ModInt res = 1, a = *this;
while (Exp) {
if (Exp & 1) res = res * a;
a = a * a;
Exp >>= 1;
}
return res;
}
ModInt inv(void) const { return pow(MOD - 2); }
ModInt & operator ++ (void) { return *this += 1; }
ModInt & operator -- (void) { return *this -= 1; }
ModInt operator ++ (int) { ModInt old = *this; operator ++(); return old; }
ModInt operator -- (int) { ModInt old = *this; operator --(); return old; }
friend ModInt operator + (const long long &x, const ModInt &y) { return ModInt(x) + y; }
friend ModInt operator - (const long long &x, const ModInt &y) { return ModInt(x) - y; }
friend ModInt operator * (const long long &x, const ModInt &y) { return ModInt(x) * y; }
friend ModInt operator / (const long long &x, const ModInt &y) { return ModInt(x) / y; }
friend ostream & operator << (ostream &out, const ModInt &x) { return out << x.val; }
friend istream & operator >> (istream &in, ModInt &x) { long long a; in >> a; x = a; return in; }
bool operator < (const ModInt &other) const { return val < other.val; }
bool operator > (const ModInt &other) const { return val > other.val; }
bool operator <= (const ModInt &other) const { return val <= other.val; }
bool operator >= (const ModInt &other) const { return val >= other.val; }
bool operator == (const ModInt &other) const { return val == other.val; }
bool operator != (const ModInt &other) const { return val != other.val; }
explicit operator bool(void) const { return val; }
explicit operator int(void) const { return val; }
ModInt operator >>= (const int &x) { return normalize((int) val >> x); }
ModInt operator >> (const int &x) const { return ModInt(*this) >>= x; }
ModInt operator <<= (const int &x) { return ModInt((long long) val << x); }
ModInt operator << (const int &x) const { return ModInt(*this) <<= x; }
ModInt operator &= (const int &x) { return normalize((int) val & x); }
ModInt operator & (const int &x) const { return ModInt(*this) &= x; }
ModInt operator |= (const int &x) { return ModInt((int) val | x); }
ModInt operator | (const int &x) const { return ModInt(*this) |= x; }
ModInt operator ^= (const int &x) { return ModInt((int) val ^ x); }
ModInt operator ^ (const int &x) const { return ModInt(*this) ^= x; }
ModInt operator ~ (void) const { return ModInt(~val); }
};
using Modular = ModInt <MOD>;
}
using namespace Mod;
typedef pair <int, Modular> pil;
pil operator + (const pil & a, const pil & b) {
if (a.fi == b.fi) return make_pair(a.fi, a.se + b.se);
return a.fi > b.fi ? a : b;
}
// index from 0
template <class T>
struct Fenwick {
T *bit;
int n = -1;
Fenwick(int _n = 0) {
resize(_n);
}
void reset(void) {
fill(bit, bit + 1 + n, T(0, 0));
}
void resize(int _n) {
if (~n) delete bit;
n = _n;
bit = new T[n + 1];
reset();
}
void update(int i, T val) {
assert(0 <= i);
++i;
for (; i <= n; i += i & -i) bit[i] = bit[i] + val;
}
void update(int l, int r, T val) {
if (l > r) return;
update(l, val);
update(r + 1, -val);
}
T get(int i) {
if (i < 0) return T(0, 0);
++i;
i = min(i, n);
T res(0, 0);
for (; i > 0; i -= i & -i)
res = res + bit[i];
return res;
}
T get(int l, int r) {
if (l > r) return T(0, 0);
return get(r) - get(l - 1);
}
int upper_bound(T val) {
int res = 0;
for (int i = __lg(n); i >= 0; --i) {
if ((res | MASK(i)) <= n && val >= bit[res | MASK(i)]) {
res |= MASK(i);
val -= bit[res];
}
}
return res;
}
int lower_bound(T val) {
int res = 0;
for (int i = __lg(n); i >= 0; --i) {
if ((res | MASK(i)) <= n && val > bit[res | MASK(i)]) {
res |= MASK(i);
val -= bit[res];
}
}
return res;
}
};
int N, A[MAX];
void init(void) {
cin >> N;
for (int i = 1; i <= N; ++i) cin >> A[i];
}
void process(void) {
compress(A + 1, A + 1 + N, A + 1);
Fenwick <pil> inc(N + 1), dec(N + 1);
pil res(0, 0);
inc.update(0, make_pair(0, 1));
dec.update(0, make_pair(0, 1));
for (int i = N; i; --i) {
pil longest_inc = inc.get(A[i] - 1);
pil longest_dec = dec.get(N - A[i]);
int len = longest_inc.fi + longest_dec.fi + 1;
res = res + make_pair(len, longest_inc.se * longest_dec.se * Modular(2).pow(N - len));
inc.update(A[i], make_pair(longest_inc.fi + 1, longest_inc.se));
dec.update(N - A[i] + 1, make_pair(longest_dec.fi + 1, longest_dec.se));
// cout << i << ' ' << A[i] << ' ' << longest_inc << ' ' << longest_dec << '\n';
}
cout << res.fi << ' ' << res.se << '\n';
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
file("coci1617_r3_zoltan");
init();
process();
// cerr << "Time elapsed: " << TIME << " s.\n";
return (0^0);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||