Submission #541171

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
541171	2022-03-22T14:23:38 Z	akhan42	Zoltan (COCI16_zoltan)	C++17	140 / 140	188 ms	8560 KB

zoltan

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int MX = 200 * 1000 + 5;
int mod = 1000 * 1000 * 1000 + 7;
vi indexes, a;


int mult(int a, int b) {
	return 1ll * a * b % mod;
}

int add(int a, int b) {
	return (a + b) % mod;
}

int binpow(int x, int deg) {
	int r = 1;
	for(; deg; deg >>= 1, x = mult(x, x))
		if(deg & 1)
			r = mult(r, x);
	return r;
}


struct Node {
	int d = 0, ct = 0;

	Node() {}

	Node(int d, int ct): d(d), ct(ct) {}

	static Node comb(Node a, Node b) {
		if(a.d < b.d) {
			return b;
		}
		else if(a.d == b.d) {
			return Node(a.d, add(a.ct, b.ct));
		}
		else {
			return a;
		}
	}

	void addm(int de, int cte) {
		d += de;
		ct = add(ct, cte);
	}
};


struct Seg {
	int n;
	vector<Node> mx;

	Seg(int n): n(n) {
		mx.resize(2 * n);
	}

	Node query(int l, int r) {
		Node res;
		for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) res = Node::comb(res, mx[l++]);
			if(r & 1) res = Node::comb(res, mx[--r]);
		}
		return res;
	}

	void update(int p, Node v) {
		mx[p += n] = v;
		for(; p > 1; p >>= 1) {
			mx[p >> 1] = Node::comb(mx[p], mx[p ^ 1]);
		}
	}

	Node at(int i) {
		return query(i, i);
	}
};


bool cmp1(int i, int j) {
	return mp(-a[i], i) < mp(-a[j], j);
}


bool cmp2(int i, int j) {
	return mp(a[i], i) < mp(a[j], j);
}


void solve() {
	int n;
	cin >> n;
	a.resize(n);
	forn(i, n) {
		cin >> a[i];
		indexes.pb(i);
	}
	sort(all(indexes), cmp1);
	Seg seg(n);

	for(int i: indexes) {
		Node q = seg.query(i, n - 1);
		q.addm(1, q.d == 0 ? 1 : 0);
		seg.update(i, q);
	}

	sort(all(indexes), cmp2);
	Seg seg2(n);

	int ad = -1, act = 0;
	for(int i: indexes) {
		Node q = seg2.query(i, n - 1);
		q.addm(1, q.d == 0 ? 1 : 0);
		seg2.update(i, q);

		Node q2 = seg.at(i);
		int dep = q.d + q2.d - 1, ct = mult(q.ct, q2.ct);
		ct = mult(ct, binpow(2, n - dep));

		if(dep > ad)
			ad = dep, act = ct;
		else if(dep == ad)
			act = add(act, ct);
	}

	cout << ad << ' ' << act << '\n';
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

//	freopen("slingshot.in", "r", stdin);
//	freopen("slingshot.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		solve();
	}
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	356 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	328 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	139 ms	6896 KB	Output is correct
12	Correct	107 ms	6132 KB	Output is correct
13	Correct	99 ms	5664 KB	Output is correct
14	Correct	126 ms	6104 KB	Output is correct
15	Correct	178 ms	7424 KB	Output is correct
16	Correct	188 ms	8560 KB	Output is correct
17	Correct	157 ms	8480 KB	Output is correct
18	Correct	153 ms	8520 KB	Output is correct
19	Correct	172 ms	8520 KB	Output is correct
20	Correct	169 ms	8444 KB	Output is correct