Submission #802484

#	Time	Username	Problem	Language	Result	Execution time	Memory
802484		rxlfd314	Financial Report (JOI21_financial)	C++17	100 / 100	373 ms	26828 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;
	}
	
	struct Segtree {
		vector<int> sgt;
		Segtree(int n) {
			sgt.resize(n<<2, 0);
		}
		void upd(int p, int v, int i = 1, int tl = 0, int tr = -1) {
			if (tr < 0) tr += sgt.size() >> 2;
			if (tl == tr) {
				sgt[i] = max(sgt[i], v);
			} else {
				int tm = tl + tr >> 1;
				p > tm ? upd(p, v, i<<1|1, tm+1, tr) : upd(p, v, i<<1, tl, tm);
				sgt[i] = max(sgt[i<<1], sgt[i<<1|1]);
			}
		}
		int qry(int ql, int qr, int i = 1, int tl = 0, int tr = -1) {
			if (tr < 0) tr += sgt.size() >> 2;
			if (tl > qr || tr < ql) return 0;
			if (ql <= tl && tr <= qr) return sgt[i];
			int tm = tl + tr >> 1;
			return max(qry(ql, qr, i<<1, tl, tm), qry(ql, qr, i<<1|1, tm+1, tr));
		}
	} sgt(N);
	
	vector<int> ord(N);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](const int &a, const int &b) {
		return A[a] != A[b] ? A[a] < A[b] : a > b;		
	});
	
	struct DSU {
		vector<int> uf, L;
		DSU(int n) {uf.resize(n, -1); L.resize(n, 0); iota(L.begin(), L.end(), 0);}
		int find(int f) {return uf[f] < 0 ? f : uf[f] = find(uf[f]);}
		void unite(int a, int b) {
			if ((a = find(a)) == (b = find(b))) return;
			if (uf[a] > uf[b]) swap(a, b);
			uf[a] += uf[b], uf[b] = a;
			L[a] = min(L[a], L[b]);
		}
		int getL(int i) {return L[find(i)];}
	} uf(N);
	
	set<int> in;
	for (int i : ord) {
		auto it = in.lower_bound(i);
		if (it != in.end() && *it - D <= i) {
			uf.unite(*it, i);
		}
		if (it != in.begin() && *--it + D >= i) {
			uf.unite(*it, i);
		}
		sgt.upd(i, sgt.qry(uf.getL(i), i) + 1);
		in.insert(i);
	}
	cout << sgt.qry(0, N-1) << '\n';
}

Compilation message (stderr)

Main.cpp: In member function 'void main()::Segtree::upd(int, int, int, int, int)':
Main.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
Main.cpp: In member function 'int main()::Segtree::qry(int, int, int, int, int)':
Main.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |    int tm = tl + tr >> 1;
      |             ~~~^~~~

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