oj.uz

답안 #680482

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680482 2023-01-11T00:49:18 Z GusterGoose27 Zoltan (COCI16_zoltan) C++11
91 / 140
 500 ms 41512 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];
pii downseq[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--) {
		downseq[i] = tree->query(0, seq[i]-1);
		downseq[i].first++;
		if (downseq[i].second == 0) downseq[i].second++;
		tree->upd(seq[i], downseq[i]);
		ans = comb(ans, pii(upseq[i].first+downseq[i].first-1, ((ll)upseq[i].second*downseq[i].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
91.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 544 KB Output is correct
11 Runtime error 253 ms 33096 KB Memory limit exceeded
12 Correct 233 ms 28756 KB Output is correct
13 Correct 202 ms 27124 KB Output is correct
14 Correct 310 ms 28904 KB Output is correct
15 Runtime error 479 ms 35892 KB Memory limit exceeded
16 Runtime error 500 ms 41512 KB Memory limit exceeded
17 Runtime error 300 ms 35592 KB Memory limit exceeded
18 Runtime error 281 ms 35700 KB Memory limit exceeded
19 Runtime error 282 ms 35532 KB Memory limit exceeded
20 Runtime error 296 ms 35648 KB Memory limit exceeded