oj.uz

답안 #366048

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
366048 2021-02-12T20:17:09 Z cheissmart Zoltan (COCI16_zoltan) C++14
21 / 140
 570 ms 16872 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("trapv")
#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 0 ms 364 KB Output isn't correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Incorrect 2 ms 492 KB Output isn't correct
8 Incorrect 3 ms 492 KB Output isn't correct
9 Incorrect 2 ms 492 KB Output isn't correct
10 Incorrect 2 ms 492 KB Output isn't correct
11 Incorrect 353 ms 14844 KB Output isn't correct
12 Incorrect 313 ms 14184 KB Output isn't correct
13 Incorrect 284 ms 9724 KB Output isn't correct
14 Incorrect 362 ms 14056 KB Output isn't correct
15 Incorrect 492 ms 15456 KB Output isn't correct
16 Incorrect 570 ms 16488 KB Output isn't correct
17 Incorrect 459 ms 16488 KB Output isn't correct
18 Incorrect 467 ms 16872 KB Output isn't correct
19 Incorrect 477 ms 16616 KB Output isn't correct
20 Incorrect 461 ms 16700 KB Output isn't correct