Submission #488773

#	Time	Username	Problem	Language	Result	Execution time	Memory
488773		grt	Bubble Sort 2 (JOI18_bubblesort2)	C++17	17 / 100	9048 ms	2256 KiB

bubblesort2

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

typedef tree<pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n, q;
ordered_set S;
map<int,int>occ;

vi countScans(vi A, vi X, vi V) {
	n = (int)A.size(); q = (int)X.size();
	vi ans(q);
	for(int i = 0; i < q; ++i) {
		A[X[i]] = V[i];
		S.clear();
		occ.clear();
		ans[i] = 0;
		for(int j = 0; j < n; ++j) {
			int x = S.order_of_key({-A[j], -1});
			ans[i] = max(ans[i], x);
			S.insert({-A[j], occ[A[j]]++});
		}
	}
	return ans;	
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//cin >> n >> q;
	//vi A(n), X(q), V(q);
	//for(int i = 0; i < n; ++i) cin >> A[i];
	//for(int i = 0; i < q; ++i) cin >> X[i] >> V[i];
	//vi ans = countScans(A, X, V);
	//for(int x : ans) {
		//cout << x << "\n";
	//}
//}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40