oj.uz

Submission #961586

# Submission time Handle Problem Language Result Execution time Memory
961586 2024-04-12T08:36:24 Z 0npata Crossing (JOI21_crossing) C++17
0 / 100
 0 ms 344 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -