oj.uz

답안 #366041

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
366041 2021-02-12T19:54:48 Z cheissmart Zoltan (COCI16_zoltan) C++14
21 / 140
 350 ms 22756 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << (x) << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7, M = 1e9 + 7;

int n;

pi add(pi a, pi b) {
	if(a.F > b.F) return a;
	else if(a.F < b.F) return b;
	a.S = (a.S + b.S) % M;
	return a;
}

struct seg_tree_mx {
	pi t[N * 4];
	seg_tree_mx() {
		build();
	}
	void build(int v = 1, int tl = 0, int tr = n) {
		if(tr - tl == 1) {
			t[v] = {-1, 0};
			return;
		}
		int tm = (tl + tr) / 2;
		build(v * 2, tl, tm);
		build(v * 2 + 1, tm, tr);
		t[v] = add(t[v * 2], t[v * 2 + 1]);
	}
	pi qry(int l, int r, int v = 1, int tl = 0, int tr = n) {
		if(l >= r) return {-1, 0};
		if(l <= tl && tr <= r)
			return t[v];
		int tm = (tl + tr) / 2;
		pi ans = {-1, 0};
		if(l < tm) ans = add(ans, qry(l, r, v * 2, tl, tm));
		if(r > tm) ans = add(ans, qry(l, r, v * 2 + 1, tm, tr));
		return ans;
	}
	void upd(int pos, pi val, int v = 1, int tl = 0, int tr = n) {
		if(tr - tl == 1) {
			t[v] = add(t[pos], val);
			return;
		}
		int tm = (tl + tr) / 2;
		if(pos < tm) upd(pos, val, v * 2, tl, tm);
		else upd(pos, val, v * 2 + 1, tm, tr);
		t[v] = add(t[v * 2], t[v * 2 + 1]);
	}
};

int a[N];

pi dp_up[N], dp_down[N];

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> n;

	seg_tree_mx up, down;
	vi compress;

	for(int i = 0; i < n; i++) cin >> a[i], compress.PB(a[i]);

	sort(ALL(compress));
	compress.resize(unique(ALL(compress)) - compress.begin());

	auto add_one = [&] (pi a) {
		a.F++;
		return a;
	};

	for(int i = n - 1; i >= 0; i--) {
		a[i] = lower_bound(ALL(compress), a[i]) - compress.begin();
		dp_up[i] = dp_down[i] = {1, 1};
		dp_up[i] = add(dp_up[i], add_one(up.qry(a[i] + 1, n)));
		dp_down[i] = add(dp_down[i], add_one(down.qry(0, a[i])));
		up.upd(a[i], dp_up[i]);
		down.upd(a[i], dp_down[i]);
	}

	pi ans = {-1, 0};

	auto merge = [&] (pi a, pi b) {
		pi c = MP(a.F + b.F, (ll) a.S * b.S % M);
		return c;
	};

	for(int i = 0; i < n; i++) {
		ans = add(ans, dp_up[i]);
		ans = add(ans, dp_down[i]);
	}

	V<pi> up_sum(n, MP(-1, 0)), down_sum(n, MP(-1, 0));
	for(int i = 0; i < n; i++) {
		up_sum[a[i]] = add(up_sum[a[i]], dp_up[i]);
		down_sum[a[i]] = add(down_sum[a[i]], dp_down[i]);
	}
	for(int i = n - 2; i >= 0; i--)
		up_sum[i] = add(up_sum[i], up_sum[i + 1]);
	for(int i = 1; i < n; i++)
		down_sum[i] = add(down_sum[i], down_sum[i - 1]);
	for(int i = 0; i < n - 1; i++)
		ans = add(ans, merge(down_sum[i], up_sum[i + 1]));

	int inv2 = (M + 1) / 2;

	ans.S = (ll) ans.S * inv2 % M;
	for(int i = 0; i < n - ans.F; i++)
		ans.S = (ll) ans.S * 2 % M;

	cout << ans.F << " " << ans.S << '\n';

}

Subtask #1
21.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12908 KB Output isn't correct
2 Incorrect 7 ms 12908 KB Output isn't correct
3 Incorrect 7 ms 12908 KB Output isn't correct
4 Correct 7 ms 12908 KB Output is correct
5 Correct 7 ms 12908 KB Output is correct
6 Correct 7 ms 12908 KB Output is correct
7 Incorrect 9 ms 12908 KB Output isn't correct
8 Incorrect 8 ms 12908 KB Output isn't correct
9 Incorrect 8 ms 12908 KB Output isn't correct
10 Incorrect 8 ms 12928 KB Output isn't correct
11 Incorrect 195 ms 20452 KB Output isn't correct
12 Incorrect 165 ms 19428 KB Output isn't correct
13 Incorrect 151 ms 19048 KB Output isn't correct
14 Incorrect 246 ms 19684 KB Output isn't correct
15 Incorrect 322 ms 21356 KB Output isn't correct
16 Incorrect 350 ms 22756 KB Output isn't correct
17 Incorrect 258 ms 22372 KB Output isn't correct
18 Incorrect 254 ms 22136 KB Output isn't correct
19 Incorrect 260 ms 22244 KB Output isn't correct
20 Incorrect 264 ms 22116 KB Output isn't correct