Submission #55178

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55178	2018-07-06T08:51:58 Z	polyfish	Zoltan (COCI16_zoltan)	C++14	98 / 140	115 ms	7740 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);
			}
			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, 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) {
			int 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

98.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	444 KB	Output is correct
3	Correct	2 ms	516 KB	Output is correct
4	Correct	2 ms	516 KB	Output is correct
5	Correct	2 ms	516 KB	Output is correct
6	Correct	2 ms	524 KB	Output is correct
7	Correct	3 ms	544 KB	Output is correct
8	Correct	3 ms	544 KB	Output is correct
9	Correct	2 ms	544 KB	Output is correct
10	Correct	2 ms	672 KB	Output is correct
11	Incorrect	86 ms	6232 KB	Output isn't correct
12	Incorrect	60 ms	6232 KB	Output isn't correct
13	Incorrect	70 ms	6232 KB	Output isn't correct
14	Incorrect	78 ms	6232 KB	Output isn't correct
15	Incorrect	99 ms	6676 KB	Output isn't correct
16	Incorrect	115 ms	7596 KB	Output isn't correct
17	Correct	102 ms	7740 KB	Output is correct
18	Correct	103 ms	7740 KB	Output is correct
19	Correct	99 ms	7740 KB	Output is correct
20	Correct	95 ms	7740 KB	Output is correct