oj.uz

Submission #818298

# Submission time Handle Problem Language Result Execution time Memory
818298 2023-08-10T04:19:45 Z SteGG Financial Report (JOI21_financial) C++17
0 / 100
 4000 ms 36768 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 34268 KB Output is correct
2 Incorrect 101 ms 34032 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 36768 KB Output is correct
2 Execution timed out 4029 ms 32468 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -