Submission #802087

#	Time	Username	Problem	Language	Result	Execution time	Memory
802087		rxlfd314	Financial Report (JOI21_financial)	C++17	5 / 100	405 ms	207520 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, D;
	cin >> N >> D;
	vector<int> A(N);
	for (int &i : A) {
		cin >> i;
	}

	vector<int> cmp = A;
	sort(cmp.begin(), cmp.end());
	cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());

	struct BIT {
		vector<deque<ari2>> fen;
		BIT(int n) {fen.resize(n);}
		void upd(int i, int j, int v) {
			for (; i < fen.size(); i += i+1 & -i-1) {
				for (; fen[i].size() && fen[i].back()[0] <= v; fen[i].pop_back());
				fen[i].push_back({v, j});
			}
		}
		int qry(int i, int j) {
			int ret = 0;
			for (; ~i; i -= i+1 & -i-1) {
				for (; fen[i].size() && fen[i].front()[1] < j; fen[i].pop_front());
				ret = max(ret, fen[i].size() ? fen[i].front()[0] : 0);
			}
			return ret;
		}
	} fen(cmp.size());
	
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int j = lower_bound(cmp.begin(), cmp.end(), A[i]) - cmp.begin();
		int x = fen.qry(j-1, i-D) + 1;
		ans = max(ans, x);
		fen.upd(j, i, x);
	}
	cout << ans << '\n';
}

Compilation message (stderr)

Main.cpp: In member function 'void main()::BIT::upd(int, int, int)':
Main.cpp:23:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |    for (; i < fen.size(); i += i+1 & -i-1) {
      |           ~~^~~~~~~~~~~~
Main.cpp:23:33: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   23 |    for (; i < fen.size(); i += i+1 & -i-1) {
      |                                ~^~
Main.cpp: In member function 'int main()::BIT::qry(int, int)':
Main.cpp:30:21: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   30 |    for (; ~i; i -= i+1 & -i-1) {
      |                    ~^~

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