oj.uz

Submission #366049

# Submission time Handle Problem Language Result Execution time Memory
366049 2021-02-12T20:18:54 Z cheissmart Zoltan (COCI16_zoltan) C++14
140 / 140
 365 ms 16744 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[v], 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
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 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 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 205 ms 14932 KB Output is correct
12 Correct 172 ms 14056 KB Output is correct
13 Correct 153 ms 9804 KB Output is correct
14 Correct 252 ms 14056 KB Output is correct
15 Correct 322 ms 15560 KB Output is correct
16 Correct 365 ms 16616 KB Output is correct
17 Correct 253 ms 16488 KB Output is correct
18 Correct 254 ms 16744 KB Output is correct
19 Correct 259 ms 16744 KB Output is correct
20 Correct 252 ms 16488 KB Output is correct