Submission #420533

#	Time	Username	Problem	Language	Result	Execution time	Memory
420533		hhhhaura	Financial Report (JOI21_financial)	C++14	100 / 100	738 ms	55604 KiB

Main

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))

#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)

using namespace std;

#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
struct seg {
	int n;
	vector<int> v;
	void init_(int _n) {
		n = _n;
		v.assign(2 * n + 1, 0);
	}
	int get(int L, int R) {
		return (L + R) | (L != R);
	}
	void pull(int L, int R) {
		int nd = get(L, R), mid = (L + R) / 2;
		v[nd] = max(v[get(L, mid)], v[get(mid + 1, R)]);
	}
	void modify(int L, int R, int id, int val) {
		int nd = get(L, R), mid = (L + R) / 2;
		if(L == R) v[nd] = val;
		else {
			if(id <= mid) modify(L, mid, id, val);
			else modify(mid + 1, R, id, val);
			pull(L, R);
		}
	}
	int query(int L, int R, int l, int r) {
		int nd = get(L, R), mid = (L + R) / 2;
		if(l > R || r < L) return 0;
		else if(l <= L && r >= R) return v[nd];
		else return max(query(L, mid, l, r), query(mid + 1, R, l, r));
	}
};
namespace solver {
	int n, d;
	seg val, pos;
	vector<set<pii>> s;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	vector<int> a, dp, v;
	void init_(int _n, int _d) {
		n = _n, d= _d;
		val.init_(n);
		pos.init_(n);
		s.assign(n + 1, set<pii>());
		a.assign(n + 1, 0);
		dp.assign(n + 1, 0);
		v.clear();
	}
	void insert(int x) {
		s[a[x]].insert({dp[x], x});
		pii best = *s[a[x]].rbegin();
		val.modify(1, n, a[x], best.first);
	}
	void erase(int x) {
		s[a[x]].erase(s[a[x]].find({dp[x], x}));
		pii best = (s[a[x]].size() ? *s[a[x]].rbegin() : pii(0, 0));
		val.modify(1, n, a[x], best.first);
	}
	bool check(int x, int y) {
		return pos.query(1, n, 1, x) >= y;
	}
	int solve() {
		rep(i, 1, n) v.push_back(a[i]);
		sort(all(v)), v.resize(unique(all(v)) - v.begin());
		rep(i, 1, n) a[i] = lower_bound(all(v), a[i]) - v.begin() + 1;
		rep(i, 1, n) {
			while(pq.size() && !check(pq.top().first, i)) {
				erase(pq.top().second);
				pq.pop();
			}
			dp[i] = val.query(1, n, 1, a[i] - 1) + 1;
			pos.modify(1, n, a[i], i + d);
			pq.push({a[i], i});
			insert(i);
		}
		return val.query(1, n, 1, n);
	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, d; cin >> n >> d;
	init_(n, d);
	rep(i, 1, n) cin >> a[i];
	cout << solve() << "\n";

	return 0;
}  

Compilation message (stderr)

Main.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
Main.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
      |             ^~~~
Main.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
      |                     ^~~~

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