Submission #313039

#	Time	Username	Problem	Language	Result	Execution time	Memory
313039		Falcon	Zoltan (COCI16_zoltan)	C++17	140 / 140	404 ms	10744 KiB

zoltan

#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 (stderr)

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);
      |  ^~~~~

• Subtask 1: 140 / 140