Submission #55177

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55177	2018-07-06T08:49:10 Z	polyfish	Zoltan (COCI16_zoltan)	C++14	42 / 140	91 ms	21988 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();
	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

42.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	3 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	3 ms	652 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	2 ms	800 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Correct	3 ms	932 KB	Output is correct
6	Correct	2 ms	932 KB	Output is correct
7	Runtime error	3 ms	1084 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	3 ms	1084 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	3 ms	1084 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	3 ms	1084 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	26 ms	5912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	27 ms	6680 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	23 ms	7392 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	39 ms	8912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	36 ms	11280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	59 ms	13824 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Correct	77 ms	18408 KB	Output is correct
18	Correct	91 ms	19660 KB	Output is correct
19	Correct	75 ms	20800 KB	Output is correct
20	Correct	75 ms	21988 KB	Output is correct