oj.uz

답안 #88725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
88725 2018-12-08T01:12:32 Z jasony123123 Zoltan (COCI16_zoltan) C++11
140 / 140
 199 ms 12668 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const int INF = 1e6;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */
#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/*************************COCI 16-17 R3 #5*************************/

void modd(ll &x) {
	x %= MOD;
}

const int MAXN = 200000;
int N;
int A[MAXN];
pll incr[MAXN], dcr[MAXN]; // length, #

namespace LIS {
	pll combine(pll a, pll b) {
		if (a.first == b.first)
			return{ a.first, (a.second + b.second) % MOD };
		else
			return max(a, b);
	}

	template<class T> struct BIT {
		int L;
		v<T> bit;
		BIT(int x) {
			L = x;
			bit = v<T>(L+1, { 0,0 });
		}
		void upd(int k, T val) {  // add val to index k
		//	bit[k] = combine(bit[k], val);
			for (k++; k <= L; k += (k&-k))
				bit[k] = combine(bit[k], val);
		}
		T query(int k) { // point query
			T temp = { 0,0 };
			//RFORE(i, k, 0)
			//	temp = combine(temp, bit[i]);
			for (k++; k > 0; k -= (k&-k))
				temp = combine(temp, bit[k]);
			return temp;
		}
	};

	bool cmp(int i, int j) { // assume A is the array
		return make_pair(-A[i], i) < make_pair(-A[j], j);
	}
	void calculate(int n, pll dp[]) {
		v<int> pos; // idxs sorted decreasing A value, increasing idx value
		FOR(i, 0, n) pos.push_back(i);
		sort(all(pos), cmp);
		BIT<pll> bit(n);
		for (int p : pos) {
			dp[p] = bit.query(n - 1 - p);
			dp[p].first++;
			dp[p] = combine(dp[p], { 1,1 });
			
			bit.upd(n - 1 - p, dp[p]);
		}
	}
}

pll genBest() { // length of best, # ways
	pll best = { -1,-1 };
	FOR(i, 0, N) {
		pll temp = { dcr[i].first + incr[i].first - 1, dcr[i].second*incr[i].second };
		if (temp.first > best.first)
			best = temp;
		else if (temp.first == best.first)
			best.second += temp.second;
		modd(best.second);
	}
	return best;
}

ll mpow(ll a, ll p) {
	ll ret = 1LL;
	while (p) {
		if (p & 1LL)
			ret *= a;
		a *= a;
		modd(ret);
		modd(a);
		p >>= 1;
	}
	return ret;
}

int main() {
	io();
	cin >> N;
	FOR(i, 0, N) cin >> A[i];

	LIS::calculate(N, incr);
	FOR(i, 0, N) A[i] = -A[i];
	LIS::calculate(N, dcr);

	pll best = genBest();
	cout << best.first << "\n";
	ll ways = best.second*mpow(2, N - best.first);
	modd(ways);
	cout << ways << "\n";
	return 0;
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 3 ms 600 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 120 ms 10260 KB Output is correct
12 Correct 102 ms 10260 KB Output is correct
13 Correct 91 ms 10260 KB Output is correct
14 Correct 133 ms 10260 KB Output is correct
15 Correct 174 ms 11048 KB Output is correct
16 Correct 199 ms 12456 KB Output is correct
17 Correct 169 ms 12480 KB Output is correct
18 Correct 161 ms 12668 KB Output is correct
19 Correct 162 ms 12668 KB Output is correct
20 Correct 163 ms 12668 KB Output is correct