Submission #538206

#	Time	Username	Problem	Language	Result	Execution time	Memory
538206		Cantfindme	Zoltan (COCI16_zoltan)	C++17	70 / 140	410 ms	55004 KiB

zoltan

#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 / 140