Submission #55184

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55184	2018-07-06T08:53:46 Z	polyfish	Zoltan (COCI16_zoltan)	C++14	140 / 140	173 ms	7664 KB

zoltan

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 200002;
const int MOD = 1000000007;

struct fenwick_tree {
	vector<pair<int, int> > bit;
	int n;

	fenwick_tree(int _n) {
		n = _n;
		bit.resize(n, make_pair(0, 0));
	}

	void upd(int id, pair<int, int> val) {
		for (; id<=n; id += id & (-id)) {
			if (bit[id].first==val.first)
				bit[id].second = (bit[id].second + val.second) % MOD;
			else
				bit[id] = max(bit[id], val);
		}
	}

	pair<int, int> get(int id) {
		pair<int, int> res(0, 0);
		if (id==0)
			return res;
		for (; id>0; id -= id & (-id)) {
			if (bit[id].first==res.first) {
				res.second = (res.second + bit[id].second) % MOD;
			}
			else {
				res = max(res, bit[id]);
			}
		}
		return res;
	}
};

int n, a[MAX_N];
pair<int, int> lis[MAX_N], lds[MAX_N];
vector<pair<int, int> > b;

void enter() {
	cin >> n;
	for (int i=1; i<=n; ++i)
		cin >> a[i];
}

void compress() {
	for (int i=1; i<=n; ++i)
		b.push_back(make_pair(a[i], i));
	sort(b.begin(), b.end());
	int cnt = 0;
	for (int i=0; i<b.size(); ++i) {
		if (i==0 || b[i].first!=b[i-1].first)
			++cnt;
		a[b[i].second] = cnt;
	}
}

void find_lis() {
	fenwick_tree tr(n);
	for (int i=n; i>=1; --i) {
		lis[i] = tr.get(a[i]-1);
		++lis[i].first;
		if (lis[i].second==0)
			++lis[i].second;
		tr.upd(a[i], lis[i]);
	}
}

void find_lds() {
	fenwick_tree tr(n);
	for (int i=n; i>=1; --i) {
		lds[i] = tr.get(n - a[i]);
		++lds[i].first;
		if (lds[i].second==0)
			++lds[i].second;
		tr.upd(n - a[i] + 1, lds[i]);
	}
}

int64_t pw(int n, int k) {
	if (k==0)
		return 1;
	int64_t tmp = pw(n, k/2);
	if (k%2)
		return tmp * tmp % MOD * n % MOD;
	return tmp * tmp % MOD;
}

void solve() {
	int len = 0;
	int64_t cnt = 0;
	for (int i=1; i<=n; ++i)
		len = max(len, lis[i].first + lds[i].first - 1);
	for (int i=1; i<=n; ++i) {
		if (lis[i].first + lds[i].first - 1 == len) {
			int64_t tmp = 1LL * lis[i].second * lds[i].second % MOD 
						* pw(2, n - lis[i].first - lds[i].first + 1) % MOD;
			cnt = (cnt + tmp) % MOD;
		}
	}
	cout << len << ' ' << cnt;
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	compress();
	find_lis();
	find_lds();
	solve();
}

Compilation message

zoltan.cpp: In function 'void compress()':
zoltan.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<b.size(); ++i) {
                ~^~~~~~~~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	432 KB	Output is correct
4	Correct	2 ms	536 KB	Output is correct
5	Correct	3 ms	584 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	4 ms	584 KB	Output is correct
8	Correct	3 ms	584 KB	Output is correct
9	Correct	3 ms	584 KB	Output is correct
10	Correct	3 ms	584 KB	Output is correct
11	Correct	91 ms	6112 KB	Output is correct
12	Correct	78 ms	6112 KB	Output is correct
13	Correct	71 ms	6112 KB	Output is correct
14	Correct	100 ms	6112 KB	Output is correct
15	Correct	119 ms	6680 KB	Output is correct
16	Correct	173 ms	7656 KB	Output is correct
17	Correct	123 ms	7656 KB	Output is correct
18	Correct	123 ms	7656 KB	Output is correct
19	Correct	118 ms	7656 KB	Output is correct
20	Correct	106 ms	7664 KB	Output is correct