Submission #717614

#	Time	Username	Problem	Language	Result	Execution time	Memory
717614		Radin_Zahedi2	Financial Report (JOI21_financial)	C++17	65 / 100	4077 ms	336988 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
//#define endl '\n'
     
     
int n, d;
const int N = 3e5 + 5;
const int L = (1 << 19);
int a[N];
     
int mini[N];
int dp[N];

set<pair<int, int>> seg[(L << 1)];


void addto(set<pair<int, int>> &s, pair<int, int> now) {
	s.insert(now);

	auto it = s.find(now);

	if (next(it) != s.end()) {
		if (it->se >= next(it)->se) {
			s.erase(it);
			return;
		}
	}
	
	while (s.find(now) != s.begin()) {
		auto it = s.find(now);
		if (it == s.end()) {
			throw;
		}

		if (prev(it)->se < it->se) {
			break;
		}

		s.erase(prev(it));
	}
}

int best(set<pair<int, int>> &s, int a) {
	auto it = s.lower_bound(mp(a + 1, -(n + 1)));

	if (it == s.end()) {
		return 0;
	}
	
	return it->se;
}

void upd(int ind) {
	pair<int, int> now = mp(a[ind], -dp[ind]);
	ind += L;

	while (ind) {
		addto(seg[ind], now);

		ind >>= 1;
	}
}

int get(int e, int a) {
	e++;
	e += L;

	int ans = 0;

	while (e) {
		if (e & 1) {
			e--;

			ans = min(ans, best(seg[e], a));
		}

		e >>= 1;
	}

	return ans;
}

void input() {
    cin >> n >> d;
     
    for (int i = 1; i <= n; i++) {
    	cin >> a[i];
    }
}
     
void cremini() {
    deque<int> dq;
    for (int i = 1; i < d; i++) {
    	while (!dq.empty()) {
    		if (a[dq.front()] < a[i]) {
    			break;
    		}

    		dq.pop_front();
    	}
    	dq.push_front(i);
    }
     
    for (int i = d; i <= n; i++) {
    	while (!dq.empty()) {
    		if (a[dq.front()] < a[i]) {
    			break;
    		}
     
    		dq.pop_front();
    	}
    	dq.push_front(i);
     
    	if (dq.back() == i - d) {
    		dq.pop_back();
    	}
     
    	mini[i] = a[dq.back()];
    }
     
    for (int i = d; i <= n; i++) {
    	int tri = a[i];
    	for (int j = i - d + 1; j <= i; j++) {
    		tri = min(tri, a[j]);
    	}
     
    	if (tri != mini[i]) {
    		throw;
    	}
    }
}
     
void solve() {
    cremini();
     
     
    vector<int> obs;
    for (int i = n; i >= 1; i--) {
    	int lobs = sz(obs), robs = -1;
    	while (lobs - 1 != robs) {
    		int m = (lobs + robs + 1) / 2;
     
    		if (mini[obs[m]] > a[i]) {
    			robs = m;
    		}
    		else {
    			lobs = m;
    		}
    	}
     
    	int limi = n;
    	if (robs != -1) {
    		limi = obs[robs];
    	}
    

		dp[i] = -get(limi, a[i]) + 1;
    	upd(i);

    	if (i + d - 1 <= n) {
    		while (!obs.empty()) {
    			if (mini[i + d - 1] < mini[obs.back()]) {
    				break;
    			}
    			
    			obs.pop_back();
    		}
    		obs.pb(i + d - 1);
    	}
    }
     
     
    int ans = 0;
    for (int i = 1; i <= n; i++) {
    	ans = max(ans, dp[i]);
    }
     
    cout << ans;
}
     
int main() {
    ios::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
     
    input();
     
    solve();
     
    return 0;
}

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