oj.uz

Submission #541170

# Submission time Handle Problem Language Result Execution time Memory
541170 2022-03-22T14:17:34 Z akhan42 Zoltan (COCI16_zoltan) C++17
21 / 140
 232 ms 13236 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Incorrect 1 ms 316 KB Output isn't correct
3 Incorrect 1 ms 256 KB Output isn't correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Incorrect 1 ms 328 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Incorrect 161 ms 10248 KB Output isn't correct
12 Incorrect 149 ms 8904 KB Output isn't correct
13 Incorrect 131 ms 8436 KB Output isn't correct
14 Incorrect 150 ms 9340 KB Output isn't correct
15 Incorrect 202 ms 11508 KB Output isn't correct
16 Incorrect 232 ms 13236 KB Output isn't correct
17 Incorrect 180 ms 12676 KB Output isn't correct
18 Incorrect 182 ms 12588 KB Output isn't correct
19 Incorrect 180 ms 12612 KB Output isn't correct
20 Incorrect 177 ms 12672 KB Output isn't correct