oj.uz

답안 #366046

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
366046 2021-02-12T20:11:28 Z cheissmart Zoltan (COCI16_zoltan) C++14
21 / 140
 351 ms 17000 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];
	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]);
	}
} up, down;
 
int a[N];
 
pi dp_up[N], dp_down[N];
 
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0);
 
	cin >> n;
 
	up.build(), down.build();

	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) {
		if(a.F == -1 || b.F == -1) return MP(-1, 0);
		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 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Incorrect 1 ms 492 KB Output isn't correct
8 Incorrect 2 ms 492 KB Output isn't correct
9 Incorrect 1 ms 492 KB Output isn't correct
10 Incorrect 1 ms 492 KB Output isn't correct
11 Incorrect 190 ms 15208 KB Output isn't correct
12 Incorrect 163 ms 14440 KB Output isn't correct
13 Incorrect 150 ms 10092 KB Output isn't correct
14 Incorrect 235 ms 14440 KB Output isn't correct
15 Incorrect 335 ms 15680 KB Output isn't correct
16 Incorrect 351 ms 16744 KB Output isn't correct
17 Incorrect 263 ms 16744 KB Output isn't correct
18 Incorrect 257 ms 17000 KB Output isn't correct
19 Incorrect 297 ms 16744 KB Output isn't correct
20 Incorrect 264 ms 17000 KB Output isn't correct