oj.uz

Submission #538207

# Submission time Handle Problem Language Result Execution time Memory
538207 2022-03-16T09:46:31 Z Cantfindme Zoltan (COCI16_zoltan) C++17
14 / 140
 127 ms 9712 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;

int mx;

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);
}

pi fw1[maxn], fw2[maxn];

int ls(int x) {
	return x & (-x);
}

void upd(pi *fw, int x, pi nv) {
	for (; x <= mx; x+=ls(x)) fw[x] = calc(fw[x], nv);
}

pi sum(pi *fw, int x) {
	pi res = pi(0,0);
	for (; x; x -= ls(x)) res = calc(res, fw[x]);
	return res;
}

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;
	}

	mx = v.size()+1;

	pi rans = pi(0,0);

	for (int i = n; i >= 1; i--) {
		pi aft = sum(fw1, mx - (A[i] + 1));
		pi bef = sum(fw2, A[i] - 1);

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

		if (bef.s == 0) bef.s = 1;
		bef.f += 1;
		upd(fw2, mx - 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
14.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Incorrect 1 ms 340 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 63 ms 7808 KB Output isn't correct
12 Incorrect 51 ms 6832 KB Output isn't correct
13 Incorrect 45 ms 6448 KB Output isn't correct
14 Incorrect 63 ms 6896 KB Output isn't correct
15 Incorrect 85 ms 8480 KB Output isn't correct
16 Incorrect 127 ms 9712 KB Output isn't correct
17 Incorrect 84 ms 8756 KB Output isn't correct
18 Incorrect 74 ms 8708 KB Output isn't correct
19 Incorrect 72 ms 8716 KB Output isn't correct
20 Incorrect 76 ms 8820 KB Output isn't correct