Submission #961586

#	Time	Username	Problem	Language	Result	Execution time	Memory
961586		0npata	Crossing (JOI21_crossing)	C++17	0 / 100	0 ms	344 KiB

Main

#include<bits/stdc++.h>
using namespace std;


#define vec vector
#define snd second
#define fst first
#define pb push_back

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, d;
	cin >> n >> d;
	vec<int> a(n);
	for(int i = 0; i<n; i++) {
		cin >> a[i];
	}

	map<int, int> bst;
	multiset<int> lstd;

	for(int i = 0; i<n; i++) {
		if(lstd.size() == d) {
			int mn = *lstd.begin();
			while(bst.begin() != bst.end()) {
				if((*bst.begin()).fst < mn) {
					bst.erase(bst.begin());
				}
				else {
					break;
				}
			}
		}

		auto nxt = bst.lower_bound(a[i]);
		int res;
		if(nxt == bst.begin()) {
			res = 1;
		}
		else {
			auto prev = nxt;
			prev--;
			res = (*prev).snd + 1;
		}

		vec<int> te(0);
		while(nxt != bst.end()) {
			if((*nxt).snd <= res) {
				te.pb((*nxt).fst);
			}
			nxt++;
		}

		for(int e : te) {
			bst.erase(e);
		}

		if(bst[a[i]] < res) {
			bst[a[i]] = res;
		}
		lstd.insert(a[i]);
		if(i-d >= 0) {
			lstd.erase(lstd.find(a[i-d]));
		}
	}

	int ans = (*bst.rbegin()).second;

	cout << ans << '\n';
}

Compilation message (stderr)

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

• Subtask 1: 0 / 3
• Subtask 2: 0 / 23
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51