oj.uz

답안 #55177

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55177 2018-07-06T08:49:10 Z polyfish Zoltan (COCI16_zoltan) C++14
42 / 140
 91 ms 21988 KB 
//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

# 결과 실행 시간 메모리 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