Submission #640555

#	Time	Username	Problem	Language	Result	Execution time	Memory
640555		KYoA_A	Zoltan (COCI16_zoltan)	C++17	140 / 140	151 ms	13276 KiB

zoltan

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define dbg(x...)
#endif

#define rep(i, a, b)	for(int i = a; i < (b); ++i)
#define rrep(a, b, c)	for(int a = (b); a > c; --a)
#define each(a, b)	for(auto& a : b)

#define sz(x)       (int)(x).size()
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(), (a).rend()

#define vi vector<int>
#define ar array

template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define rsz resize
#define bk back()

#define pi pair<int, int>
#define pl pair<ll, ll>
#define mp make_pair
#define f first
#define s second

#define pct(x) __builtin_popcount(x)
constexpr int fsb(int x) {return __builtin_ffs(x) - 1;} // first set bit
constexpr int log2(int x) {return x == 0 ? 0 : 31-__builtin_clz(x);} // floor(log2(x))
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

template <class T> bool umin(T& a, const T& b){return b<a?a=b, 1:0;}
template <class T> bool umax(T& a, const T& b){return a<b?a=b, 1:0;}

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

using ll = long long;
using ld = long double;
using str = string;

const int inf = (int)1e9 + 5;
const ll infl = (ll)1e18 + 5;
const ld PI = acos((ld)-1);
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/



template<class T> struct Seg { // comb(ID,b) = b
	const T ID{}; T comb(T a, T b) { 

		if(a.f != b.f) return max(a, b);
		return {a.f, (a.s + b.s)%MOD};
	}
	int n; vector<T> seg;
	void init(int _n) { 
		n = 1; 
		while(n < _n) n<<=1;
		seg.assign(2*n,ID); 
	}
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		p += n;
		seg[p] = comb(seg[p], val); for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// sum on interval [l, r]
		T ra = ID, rb = ID; 
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
};

#define int ll

void solve(istream &cin = std::cin, ostream &cout = std::cout){
	int n; cin >> n;
	vi v(n); each(x, v) cin >> x;
	vi a = v;
	sort(all(a));
	a.erase(unique(all(a)), a.end());
	each(x, v) x = lb(all(a), x) - a.begin() + 1;
	
	reverse(all(v));
	rrep(i, n-1, -1) v.eb(v[i]);



	Seg<pi> s;
	s.init(n + 2);
	s.upd(0, {0, 1});

	pi ans{};

	each(x, v){
		auto y = s.query(0, x - 1);
		y.f++;
		ans = s.comb(ans, y);
		s.upd(x, y);
	}

	int z = n - ans.f;
	ll x = ans.s;
	while(z){
		x = x*2%MOD;
		--z;
	}

	x = x*((MOD + 1)/2)%MOD;

	cout << ans.f << ' ' << x << '\n';

}

void gen(stringstream &s){
	int n = 1 + rng()%15;
	s << n << '\n';
	rep(i, 0, n) s << 1 + rng()%n << ' ';
}

void stress(istream &cin = std::cin, ostream &cout = std::cout){
	int n; cin >> n;
	vi v(n); each(x, v) cin >> x;
	vi a;

	pi ans{};

	function<void(int)> go = [&](int i){

		if(i == n){
			// dbg(a, ans)
			Seg<pi> s; s.init(n + 2); 
			s.upd(0, {0, 1});
			each(x, a){
				auto y = s.query(0, x - 1);
				y.f++;
				ans = s.comb(ans, y);
				s.upd(x, y);
			}
			return;
		}

		a.eb(v[i]); go(i + 1); a.pop_back();
		a.insert(a.begin(), v[i]);  go(i + 1); a.erase(a.begin());
	};

	a.eb(v[0]);
	go(1);
	cout << ans.s << '\n';
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();
	// stress();
	// #define STRESS
	#ifdef STRESS
		for (int cnt = 1;; cnt++)
		{
			stringstream ss, in1, out1, in2, out2;
	
			gen(ss);
	
			in1 << ss.str();
			in2 << ss.str();
	
			solve(in1, out1);
			stress(in2, out2);
	
			if (out1.str() != out2.str())
			{
				cout << "fail: " << cnt << endl;
				cout << ss.str() << endl;
				cout << "solve:" << endl;
				cout << out1.str() << endl;
				cout << "stress:" << endl;
				cout << out2.str() << endl;
	
				break;
			}
			else if (cnt % 100 == 0)
				cout << "ok: " << cnt << endl;
		}
	#endif

		// solve();
}

• Subtask 1: 140 / 140