Submission #541170

#	Time	Username	Problem	Language	Result	Execution time	Memory
541170		akhan42	Zoltan (COCI16_zoltan)	C++17	21 / 140	232 ms	13236 KiB

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 = 1, sm = 0;

	Node() {}

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

	static Node comb(Node a, Node b) {
		if(a.d < b.d) {
			return b;
		}
		else if(a.d == b.d) {
			return Node(a.d,
					(a.ct == 1 && b.ct == 1) ? 1 : add(a.ct, b.ct),
							add(mult(a.sm, b.ct), mult(a.ct, b.sm)));
		}
		else {
			return a;
		}
	}

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


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, 0, mult(q.ct, a[i]));
		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);

		Node q2 = seg.at(i);
		int dep = q.d + q2.d, ct = mult(q.ct, q2.ct);
		ct= mult(ct, binpow(2, n - dep));
//		cout << i << ' ' << q.ct << ' ' << q2.ct << ' ' << q.sm << ' ' << q2.sm << '\n';
		if(dep > ad)
			ad = dep, act = ct;
		else if(dep == ad)
			act = add(act, ct);

		q.addm(1, 0, mult(q.ct, a[i]));
		seg2.update(i, q);
	}

	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: 21 / 140