oj.uz

답안 #680481

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680481 2023-01-11T00:45:50 Z GusterGoose27 Zoltan (COCI16_zoltan) C++11
70 / 140
 659 ms 61984 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);
	}
	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 *uptree, *downtree;
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]];
	uptree = new stree(0, t-1);
	downtree = new stree(0, t-1);
	pii ans(0, 0);
	for (int i = n-1; i >= 0; i--) {
		upseq[i] = uptree->query(seq[i]+1, t-1);
		downseq[i] = downtree->query(0, seq[i]-1);
		upseq[i].first++;
		downseq[i].first++;
		if (upseq[i].second == 0) upseq[i].second++;
		if (downseq[i].second == 0) downseq[i].second++;
		uptree->upd(seq[i], upseq[i]);
		downtree->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
70.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 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 600 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Runtime error 353 ms 49088 KB Memory limit exceeded
12 Runtime error 258 ms 42624 KB Memory limit exceeded
13 Runtime error 280 ms 40156 KB Memory limit exceeded
14 Runtime error 349 ms 43180 KB Memory limit exceeded
15 Runtime error 528 ms 53496 KB Memory limit exceeded
16 Runtime error 659 ms 61984 KB Memory limit exceeded
17 Runtime error 346 ms 52652 KB Memory limit exceeded
18 Runtime error 367 ms 52604 KB Memory limit exceeded
19 Runtime error 354 ms 52676 KB Memory limit exceeded
20 Runtime error 344 ms 52520 KB Memory limit exceeded