oj.uz

답안 #680483

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680483 2023-01-11T00:50:23 Z GusterGoose27 Zoltan (COCI16_zoltan) C++11
98 / 140
 510 ms 39940 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:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	pii mx = pii(0, 0);
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int mid = (lp+rp)/2;
			l = new stree(lp, mid);
			r = new stree(mid+1, rp);
		}
	}
	void upd(int p, pii v) {
		if (lp > p || rp < p) return;
		if (lp == rp) {
			mx = comb(mx, v);
			return;
		}
		l->upd(p, v);
		r->upd(p, v);
		mx = comb(l->mx, r->mx);
	}
	void reset() {
		mx = pii(0, 0);
		if (l) {
			l->reset();
			r->reset();
		}
	}
	pii query(int lv, int rv) {
		if (lp >= lv && rp <= rv) return mx;
		if (lp > rv || rp < lv) return pii(0, 0);
		return comb(l->query(lv, rv), r->query(lv, rv));
	}
};

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
98.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 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 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 262 ms 31856 KB Output is correct
12 Correct 197 ms 27736 KB Output is correct
13 Correct 216 ms 26064 KB Output is correct
14 Correct 304 ms 27844 KB Output is correct
15 Runtime error 412 ms 34556 KB Memory limit exceeded
16 Runtime error 510 ms 39940 KB Memory limit exceeded
17 Runtime error 287 ms 34092 KB Memory limit exceeded
18 Runtime error 277 ms 34056 KB Memory limit exceeded
19 Runtime error 286 ms 34084 KB Memory limit exceeded
20 Runtime error 291 ms 34080 KB Memory limit exceeded