oj.uz

답안 #640555

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
640555 2022-09-14T21:33:13 Z KYoA_A Zoltan (COCI16_zoltan) C++17
140 / 140
 151 ms 13276 KB 
/*---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.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 90 ms 12240 KB Output is correct
12 Correct 79 ms 11676 KB Output is correct
13 Correct 69 ms 7392 KB Output is correct
14 Correct 98 ms 11720 KB Output is correct
15 Correct 121 ms 12548 KB Output is correct
16 Correct 151 ms 13276 KB Output is correct
17 Correct 108 ms 13156 KB Output is correct
18 Correct 108 ms 13128 KB Output is correct
19 Correct 108 ms 13104 KB Output is correct
20 Correct 110 ms 13228 KB Output is correct