Submission #528550

#	Time	Username	Problem	Language	Result	Execution time	Memory
528550		Ninja_Kunai	Financial Report (JOI21_financial)	C++14	65 / 100	293 ms	15356 KiB

Main

/** 
*    Author :  Nguyen Tuan Vu
*    Created : 20.02.2022
**/

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define fx(i,j,n) for(int i=(j);i<=(n);i++)
#define fn(i,j,n) for(int i=(j);i>=(n);i--)
#define fi first
#define se second
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define ALL(v) (v).begin(), (v).end()
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> ii;
typedef pair <ll, ll> li;
typedef tuple <int, int, int> tup;

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

void file(){
	#define TASK "TASK"
	freopen(TASK".inp","r",stdin);
	freopen(TASK".out","w",stdout);
}

const int Mod = 1e9 + 7;
const int N = 3e5 + 5;
const int INF = 1e9 + 7;
const ll INFLL = 1e18 + 7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r) {return l + rng() % (r - l + 1);}

int n, d, a[N], dp[7005][7005];

void sub2() {
	a[0] = -1;
	fx (i, 0, n - 1) fx (j, 0, i) fx (k, 1, min(d, n - i)) {
		int new_k = (a[i + k] >= a[j] ? i + k : j);
		maximize(dp[i + k][new_k], dp[i][j] + (a[i + k] > a[j]));
	}

	int ans = 0;
	fx (i, 0, n) maximize(ans, dp[n][i]);
	cout << ans;
}

struct Fenwick_Tree{
	vector <int> bit;

	Fenwick_Tree(int _n = 0) {
		n = _n;
		bit.resize(n + 7, 0);
	}

	void update(int x, int val) {
		for (; x <= n; x += x&-x) maximize(bit[x], val);
	}

	int get(int x) {
		int ans = 0;
		for (; x; x -= x&-x) maximize(ans, bit[x]);
		return ans;
	}
} mybit;

void sub5() {
	mybit = Fenwick_Tree(n);
	vector <int> ctz;
	fx (i, 1, n) ctz.push_back(a[i]);
	sort (ALL(ctz)); ctz.erase(unique(ALL(ctz)), ctz.end());
	int ans = 0;
	fx (i, 1, n) {
		a[i] = lower_bound(ALL(ctz), a[i]) - ctz.begin() + 1;
		int x = mybit.get(a[i] - 1) + 1;
		mybit.update(a[i], x);
		maximize(ans, x);
	}
	cout << ans;
}

void sub4() {
	multiset <int> s;
	int ans = 0;
	fn (i, n, 1) {
		stack <int> tmp;
		if (s.size()) 
			for (auto it = s.begin(); it != s.end(); ++it) 
				if (*it <= a[i]) tmp.push(*it);
				else break;
		while (tmp.size()) {
			int u = tmp.top();
			tmp.pop();
			s.erase(s.lower_bound(u));
		}
		s.insert(a[i]);
		maximize(ans, s.size());
	}
	cout << ans;
}

int f[7005];

void sub3() {
	fn (i, n, 1) {
		int lim = min(i + d, n);
		f[i] = 1;
		fx (j, i + 1, lim) 
			if (a[i] >= a[j]) lim = min(j + d, n);
			else maximize(f[i], f[j] + 1);
	}
	cout << *max_element(f + 1, f + n + 1);
}

void solve()
{
	cin >> n >> d;
	fx (i, 1, n) cin >> a[i];
	if (d == n) sub5();
	else if (d == 1) sub4();
	else if (n <= 400) sub2();
	else sub3();
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//	file();
	int T = 1;
	//cin>>T;
	while(T--)
	{
	solve();
	}
	return 0;
}
/*** DEBUG, DON'T LAZY AND DON'T ASK OTHERS MUCH ***/
/*
|----------------|
|   TRY  HARD    |
|----------------|
 (\_/)  ||
(=.-.=) ||
/> o  \>||
\  o  / ||
 \/ \/  ||
*/

Compilation message (stderr)

Main.cpp: In function 'void sub4()':
Main.cpp:100:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  100 |   if (s.size())
      |      ^
Main.cpp: In instantiation of 'bool maximize(X&, Y) [with X = int; Y = long unsigned int]':
Main.cpp:110:25:   required from here
Main.cpp:29:11: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   29 |     if (a < b) return a = b, true;
      |         ~~^~~
Main.cpp: In function 'void file()':
Main.cpp:35:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  freopen(TASK".inp","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:36:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  freopen(TASK".out","w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35