Submission #818351

#	Time	Username	Problem	Language	Result	Execution time	Memory
818351		SteGG	Financial Report (JOI21_financial)	C++17	0 / 100	4104 ms	33656 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

void open(){
	if(fopen("input.inp", "r")){
		freopen("input.inp", "r", stdin);
		//freopen("output.out", "w", stdout);
	}
}

const int maxn = 3e5 + 5;
const int inf = 1e9 + 7;

int n, d;
int arr[maxn];
int dp[maxn];

struct Node{
	int val = 0, min_val = inf, max_val = 0;
	Node(){}
	Node(int _val, int _min_val, int _max_val) : val(_val), min_val(_min_val), max_val(_max_val) {}

	Node operator+(const Node &other){
		Node result;
		result.val = max(val, other.val);
		result.min_val = min(min_val, other.min_val);
		result.max_val = max(max_val, other.max_val);
		return result;
	}
};

struct Segtree{
	vector<Node> st;
	Segtree(int _len){
		st.resize(_len * 4);
	}

	void update(int l, int r, int id, int p){
		if(l == r){
			st[id - 1] = Node(dp[p], arr[p], arr[p]);
			return ;
		}

		int mid = (l + r) >> 1;
		if(p <= mid){
			update(l, mid, 2*id, p);
		}else{
			update(mid + 1, r, 2*id + 1, p);
		}

		st[id - 1] = st[2*id - 1] + st[2*id];
	}

	int get(int l, int r, int id, int u, int v, int p){
		if(l > v || r < u) return 0;
		if(u <= l && r <= v){
			if(st[id - 1].max_val < arr[p]) return st[id - 1].val;
			else if(st[id - 1].min_val >= arr[p]) return 0;
		}
		int mid = (l + r) >> 1;

		int left = get(l, mid, 2*id, u, v, p);
		int right = get(mid + 1, r, 2*id + 1, u, v, p);

		return max(left, right);
	}
};

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	open();
	cin >> n >> d;
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
	}

	Segtree st(n);

	deque<int> dq;
	dp[1] = 1;
	dq.push_back(1);
	// st.update(1, n, 1, 1);
	int result = 0;
	for(int i = 2; i <= n; i++){
		// dp[i] = 1 + st.get(1, n, 1, dq.front(), dq.back(), i);
		// cout << "ST : " << st.get(1, n, 1, dq.front(), dq.back(), i) << " " << dq.front() << " " << dq.back() << endl;
		dp[i] = 1;
		for(auto it = dq.begin(); it != dq.end(); it++){
			if(arr[*it] < arr[i]){
				dp[i] = max(dp[i], dp[*it] + 1);
			}
		}

		// st.update(1, n, 1, i);

		dq.push_back(i);

		while(dq.size() > d){
			dq.pop_front();
		}

		result = max(result, dp[i]);
	}

	cout << result << endl;

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:101:19: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  101 |   while(dq.size() > d){
      |         ~~~~~~~~~~^~~
Main.cpp: In function 'void open()':
Main.cpp:8:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |   freopen("input.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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