oj.uz

Submission #538206

# Submission time Handle Problem Language Result Execution time Memory
538206 2022-03-16T09:36:53 Z Cantfindme Zoltan (COCI16_zoltan) C++17
70 / 140
 410 ms 55004 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

const int maxn = 200010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;

pi calc(pi a, pi b) {
	if (a.f == b.f) return pi(a.f, (a.s + b.s) % mod);
	else return max(a, b);
}

struct node {
	int s, m, e;
	pi v = pi(0,0);
	node *l, *r;
	node (int _s, int _e) {
		s = _s; e = _e; m = (s+e)/2;
		if (s != e) {
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}

	void upd(int x, pi nv) {
		if (s == e) v = calc(v,nv);
		else {
			if (x > m) r -> upd(x,nv);
			else if (x <= m) l -> upd(x,nv);
			v = calc(l -> v, r -> v);
		}
	}

	pi rmq(int x, int y) {
		if (s == x and e == y) return v;
		else {
			if (x > m) return r -> rmq(x,y);
			else if (y <= m ) return l -> rmq(x,y);
			else return calc(l -> rmq(x,m), r -> rmq(m+1,y));
		}
	}
} *root, *root2;

int n;
int A[maxn];

int32_t main() {
	FAST
	// ifstream cin("input.txt");

	cin >> n;
	vector <int> v;
	for (int i = 1; i <= n;i++) {
		cin >> A[i];
		v.push_back(A[i]);
	}

	sort(all(v));
	v.resize(unique(v.begin(),v.end()) - v.begin());
	for (int i = 1; i<=n;i++) {
		A[i] = lower_bound(all(v), A[i]) - v.begin() + 1;
	}

	int mx = v.size()+1;
	root = new node(0, mx);
	root2 = new node(0, mx);

	pi rans = pi(0,0);

	for (int i = n; i >= 1; i--) {
		pi aft = root -> rmq(A[i]+1, mx);
		pi bef = root2 -> rmq(0, A[i]-1);

		if (aft.s == 0) aft.s = 1;
		aft.f += 1;
		root -> upd(A[i], aft);

		if (bef.s == 0) bef.s = 1;
		bef.f += 1;
		root2 -> upd(A[i], bef);
	
		rans = calc(rans, pi(bef.f + aft.f - 1, bef.s * aft.s));
	}

	for (int i = 0; i < n - rans.f; i++) {
		rans.s *= 2;
		rans.s %= mod;
	}

	cout << rans.f << " " << rans.s << "\n";
}

Subtask #1
70.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 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 2 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Runtime error 195 ms 43536 KB Memory limit exceeded
12 Runtime error 167 ms 37808 KB Memory limit exceeded
13 Runtime error 159 ms 35656 KB Memory limit exceeded
14 Runtime error 258 ms 38212 KB Memory limit exceeded
15 Runtime error 361 ms 47452 KB Memory limit exceeded
16 Runtime error 410 ms 55004 KB Memory limit exceeded
17 Runtime error 237 ms 46572 KB Memory limit exceeded
18 Runtime error 234 ms 46568 KB Memory limit exceeded
19 Runtime error 232 ms 46520 KB Memory limit exceeded
20 Runtime error 219 ms 46608 KB Memory limit exceeded