oj.uz

답안 #366047

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
366047 2021-02-12T20:13:57 Z cheissmart Zoltan (COCI16_zoltan) C++14
21 / 140
 353 ms 16648 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 = 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 0 ms 364 KB Output isn't correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Incorrect 2 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 202 ms 15032 KB Output isn't correct
12 Incorrect 170 ms 14080 KB Output isn't correct
13 Incorrect 151 ms 9708 KB Output isn't correct
14 Incorrect 230 ms 14184 KB Output isn't correct
15 Incorrect 295 ms 15500 KB Output isn't correct
16 Incorrect 353 ms 16488 KB Output isn't correct
17 Incorrect 270 ms 16616 KB Output isn't correct
18 Incorrect 274 ms 16648 KB Output isn't correct
19 Incorrect 257 ms 16508 KB Output isn't correct
20 Incorrect 254 ms 16616 KB Output isn't correct