oj.uz

답안 #680484

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680484 2023-01-11T00:51:58 Z GusterGoose27 Zoltan (COCI16_zoltan) C++11
133 / 140
 481 ms 33600 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5;
const int MOD = 1e9+7;
int n;
int seq[MAXN];
map<int, int> compress;
typedef pair<int, int> pii;
typedef long long ll;
int t = 0;

pii comb(pii a, pii b) {
	if (a.first == b.first) return pii(a.first, (a.second+b.second)%MOD);
	return max(a, b);
}

class stree {
public:
	stree *l = nullptr;
	stree *r = nullptr;
	pii mx = pii(0, 0);
	stree(int lv, int rv) {
		if (lv < rv) {
			int mid = (lv+rv)/2;
			l = new stree(lv, mid);
			r = new stree(mid+1, rv);
		}
	}
	void upd(int p, pii v, int lp = 0, int rp = t-1) {
		if (lp > p || rp < p) return;
		if (lp == rp) {
			mx = comb(mx, v);
			return;
		}
		int mid = (lp+rp)/2;
		l->upd(p, v, lp, mid);
		r->upd(p, v, mid+1, rp);
		mx = comb(l->mx, r->mx);
	}
	void reset() {
		mx = pii(0, 0);
		if (l) {
			l->reset();
			r->reset();
		}
	}
	pii query(int lv, int rv, int lp = 0, int rp = t-1) {
		if (lp >= lv && rp <= rv) return mx;
		if (lp > rv || rp < lv) return pii(0, 0);
		int mid = (lp+rp)/2;
		return comb(l->query(lv, rv, lp, mid), r->query(lv, rv, mid+1, rp));
	}
};

stree *tree;
pii upseq[MAXN];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	set<int> vals;
	for (int i = 0; i < n; i++) {
		cin >> seq[i];
		vals.insert(seq[i]);
	}
	for (int v: vals) {
		compress[v] = t++;
	}
	for (int i = 0; i < n; i++) seq[i] = compress[seq[i]];
	tree = new stree(0, t-1);
	pii ans(0, 0);
	for (int i = n-1; i >= 0; i--) {
		upseq[i] = tree->query(seq[i]+1, t-1);
		upseq[i].first++;
		if (upseq[i].second == 0) upseq[i].second++;
		tree->upd(seq[i], upseq[i]);
	}
	tree->reset();
	for (int i = n-1; i >= 0; i--) {
		pii downseq = tree->query(0, seq[i]-1);
		downseq.first++;
		if (downseq.second == 0) downseq.second++;
		tree->upd(seq[i], downseq);
		ans = comb(ans, pii(upseq[i].first+downseq.first-1, ((ll)upseq[i].second*downseq.second)%MOD));
	}
	for (int i = 0; i < n-ans.first; i++) ans.second = (2*ans.second)%MOD;
	cout << ans.first << " " << ans.second << "\n";
}

Subtask #1
133.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 508 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 221 ms 26820 KB Output is correct
12 Correct 211 ms 23460 KB Output is correct
13 Correct 186 ms 21964 KB Output is correct
14 Correct 285 ms 23400 KB Output is correct
15 Correct 392 ms 29056 KB Output is correct
16 Runtime error 481 ms 33600 KB Memory limit exceeded
17 Correct 321 ms 28760 KB Output is correct
18 Correct 257 ms 28824 KB Output is correct
19 Correct 279 ms 28736 KB Output is correct
20 Correct 297 ms 28788 KB Output is correct