Submission #575302

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
575302	2022-06-10T06:38:46 Z	BackNoob	Zoltan (COCI16_zoltan)	C++14	140 / 140	106 ms	7156 KB

zoltan

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

void add(int &a, int b)
{
	a += b;
	if(a >= mod)
		a -= mod;
}
 
struct fenwick{
	int n;
	vector<int> bit, cnt;
	fenwick(){}
	fenwick(int _n) {
		n = _n;
		bit.resize(n + 7, 0);
		cnt.resize(n + 7, 0);
	}

	void update(int pos, int val, int way)
	{
		for(; pos <= n; pos += pos & -pos) {
			if(maximize(bit[pos], val) == true) cnt[pos] = way;
			else if(bit[pos] == val) add(cnt[pos], way);
		}
	}

	pair<int, int> getans(int pos)
	{
		pair<int, int> res = {-1, 0};
		for(; pos > 0; pos -= pos & -pos) {
			if(maximize(res.fi, bit[pos]) == true) res.se = cnt[pos];
			else if(res.fi == bit[pos]) add(res.se, cnt[pos]);
		}
		return res;
	}
} ft;

int n;
int a[mxN];
pair<int, int> dp1[mxN];
pair<int, int> dp2[mxN];


void solve()
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];

	vector<int> val;
	for(int i = 1; i <= n; i++) val.pb(a[i]);
	sort(all(val));
	val.erase(unique(all(val)), val.end());
	for(int i = 1; i <= n; i++) 
		a[i] = lower_bound(all(val), a[i]) - val.begin() + 1;

	ft = fenwick(n);
	for(int i = n; i >= 1; i--) {
		maximize(dp1[i], make_pair(1, 1));

		pair<int, int> tmp = ft.getans(a[i] - 1);
		// cout << dp1[a[i]].fi << endl;
		if(maximize(dp1[i].fi, tmp.fi + 1) == true) {
			dp1[i].se = tmp.se;
		}
		else {
			if(dp1[i].fi == tmp.fi + 1)
				add(dp1[i].se, tmp.se);
		}

		ft.update(a[i], dp1[i].fi, dp1[i].se);
	}

	ft = fenwick(n);

	for(int i = n; i >= 1; i--) {
		maximize(dp2[i], make_pair(1, 1));
		pair<int, int> tmp = ft.getans(n - a[i] + 1 - 1);

		if(maximize(dp2[i].fi, tmp.fi + 1) == true) dp2[i].se = tmp.se;
		else if(dp2[i].fi == tmp.fi + 1) add(dp2[i].se, tmp.se);
		ft.update(n - a[i] + 1, dp2[i].fi, dp2[i].se);
	}


	pair<int, int> ans = {-1, 0};
	for(int i = n; i >= 1; i--) {
		if(maximize(ans.fi, dp1[i].fi + dp2[i].fi - 1) == true) {
			ans.se = 1LL * dp1[i].se * dp2[i].se % mod;
		}
		else {
			if(ans.fi == dp1[i].fi + dp2[i].fi - 1) {
				add(ans.se, 1LL * dp1[i].se * dp2[i].se % mod);
			}
		}
	}

	// for(int i = 1; i <= n; i++) 
		// cout << dp1[a[i]].fi << ' ' << dp2[a[i]].fi << endl;

	// cout << ans.se << endl;
	for(int i = 1; i <= n - ans.fi; i++) ans.se = 1LL * ans.se * 2 % mod;
	cout << ans.fi << ' ' << ans.se << endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".in" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);
 
    int tc = 1;
    // cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	56 ms	5732 KB	Output is correct
12	Correct	51 ms	5196 KB	Output is correct
13	Correct	46 ms	4812 KB	Output is correct
14	Correct	66 ms	5152 KB	Output is correct
15	Correct	87 ms	6276 KB	Output is correct
16	Correct	106 ms	7052 KB	Output is correct
17	Correct	74 ms	7120 KB	Output is correct
18	Correct	82 ms	7156 KB	Output is correct
19	Correct	73 ms	7064 KB	Output is correct
20	Correct	72 ms	7128 KB	Output is correct