Submission #769746

#	Time	Username	Problem	Language	Result	Execution time	Memory
769746		raysh07	Financial Report (JOI21_financial)	C++17	5 / 100	747 ms	117764 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n, d;
const int N = 3e5 + 69;
multiset <int> holy[N];
vector <pair<int, int>> rem[N];
int a[N], dp[N], seg[4 * N][2]; //one for transitions, one for findlast index to keep transition till

void upd(int l, int r, int pos, int qp, int v, int i){
	if (l == r){
		if (i == 1 && v > 0){
			holy[l].insert(v);
			seg[pos][i] = *(--holy[l].end());
		} else if (i == 1 && v < 0){
			holy[l].erase(holy[l].find(-v));
			seg[pos][i] = *(--holy[l].end());
		} else {
			seg[pos][i] = v;
		}
		return;
	}

	int m = (l + r)/2;
	if (qp <= m) upd(l, m, pos*2, qp, v, i);
	else upd(m + 1, r, pos*2 + 1, qp, v, i);

	seg[pos][i] = max(seg[pos * 2][i], seg[pos * 2 + 1][i]);
}

int query(int l, int r, int pos, int ql, int qr, int i){
	if (l >= ql && r <= qr) return seg[pos][i];
	else if (l > qr || r < ql) return 0;

	int m = (l + r)/2;
	return max(query(l, m, pos*2, ql, qr, i), query(m + 1, r, pos*2 + 1, ql, qr, i));
}

int findfirst(int l, int r, int pos, int ql, int v, int i){
	if (seg[pos][i] <= v || r < ql) return -1;

	if (l == r) return l;

	int m = (l + r)/2;
	int ok = findfirst(l, m, pos*2, ql, v, i);
	if (ok == -1) ok = findfirst(m + 1, r, pos*2 + 1, ql, v, i);
	return ok;
}

void Solve()
{
	cin >> n >> d;
	for (int i = 1; i <= n; i++) cin >> a[i], holy[i].insert(0);
	d++;

	set <int> ok; map <int, int> mp; int pr = 0;
	for (int i = 1; i <= n; i++) ok.insert(a[i]);
	for (auto x : ok) mp[x] = ++pr;
	for (int i = 1; i <= n; i++) a[i] = mp[a[i]];

	multiset <int> st;
	for (int i = 1; i <= n; i++){
		st.insert(a[i]);
		if (st.size() == d) {
			upd(1, n, 1, i, *st.begin(), 0);
			st.erase(st.find(a[i - d + 1]));
		}
	}

	int ans = 0;

	for (int i = 1; i <= n; i++){
		dp[i] = query(1, n, 1, 1, a[i] - 1, 1) + 1;
		for (auto [x, y] : rem[i]){
			upd(1, n, 1, x, -y, 1);
		}
		ans = max(ans, dp[i]);
		upd(1, n, 1, a[i], dp[i], 1);

		int p1 = findfirst(1, n, 1, i, a[i], 0);
		if (p1 != -1)
		rem[p1].push_back({a[i], dp[i]});
		
	//	cout << dp[i] << " \n"[i == n];
	}
	
	cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void Solve()':
Main.cpp:69:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   69 |   if (st.size() == d) {
      |       ~~~~~~~~~~^~~~

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