oj.uz

답안 #88724

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
88724 2018-12-08T01:09:38 Z jasony123123 Zoltan (COCI16_zoltan) C++11
70 / 140
 1000 ms 8876 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, { 0,0 });
		}
		void upd(int k, T val) {  // add val to index 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]);
			return temp;
		}
	};

	//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
	//		for (k++; k <= L; k += (k&-k))
	//			bit[k] = combine(bit[k], val);
	//	}
	//	T query(int k) { // point query
	//		T temp = { 1,1 };
	//		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
70.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 2 ms 472 KB Output is correct
6 Correct 2 ms 476 KB Output is correct
7 Correct 4 ms 528 KB Output is correct
8 Correct 5 ms 564 KB Output is correct
9 Correct 4 ms 608 KB Output is correct
10 Correct 4 ms 648 KB Output is correct
11 Execution timed out 1068 ms 5812 KB Time limit exceeded
12 Execution timed out 1066 ms 5812 KB Time limit exceeded
13 Execution timed out 1062 ms 5812 KB Time limit exceeded
14 Execution timed out 1008 ms 6236 KB Time limit exceeded
15 Execution timed out 1087 ms 7540 KB Time limit exceeded
16 Execution timed out 1071 ms 8876 KB Time limit exceeded
17 Execution timed out 1077 ms 8876 KB Time limit exceeded
18 Execution timed out 1087 ms 8876 KB Time limit exceeded
19 Execution timed out 1076 ms 8876 KB Time limit exceeded
20 Execution timed out 1068 ms 8876 KB Time limit exceeded