Submission #520004

#	Time	Username	Problem	Language	Result	Execution time	Memory
520004		akhan42	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	5102 ms	1520 KiB

bubblesort2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int INF = 1000 * 1000 * 1000;


struct Seg {
	int n;
	vii p1;
	vii p2;

	Seg(int n, vii &vals) {
		this->n = n;
		p1.resize(4 * n);
		p2.resize(4 * n);

		build(vals);
	}

	bool can(ii pl, ii pr) {
		return pl.S <= pr.F;
	}

	void pull(int v) {
		int lc = 2 * v, rc = 2 * v + 1;
		if(can(p1[lc], p1[rc])) {
			p1[v] = {p1[lc].F, p1[rc].S};
		} else if(can(p1[lc], p2[rc])) {
			p1[v] = {p1[lc].F, p2[rc].S};
		} else {
			p1[v] = {-1, INF};
		}

		if(can(p2[lc], p1[rc])) {
			p2[v] = {p2[lc].F, p1[rc].S};
		} else if(can(p2[lc], p2[rc])) {
			p2[v] = {p2[lc].F, p2[rc].S};
		} else {
			p2[v] = {-1, INF};
		}
	}

	void build(vii &vals, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;

		if(tl == tr) {
			p1[v] = {vals[tl].F, vals[tl].F};
			p2[v] = {vals[tl].S, vals[tl].S};
			return;
		}
		int tm = (tl + tr) / 2;

		build(vals, 2 * v, tl, tm);
		build(vals, 2 * v + 1, tm + 1, tr);

		pull(v);
	}

	void set(int p, ii val, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;

		if(tl == tr) {
			p1[v] = {val.F, val.F};
			p2[v] = {val.S, val.S};
			return;
		}
		int tm = (tl + tr) / 2;

		if(p <= tm)
			set(p, val, 2 * v, tl, tm);
		else
			set(p, val, 2 * v + 1, tm + 1, tr);
		pull(v);
	}

	bool is_increasing() {
		return p1[1].F != -1;
	}
};


int solve_lin(vi &a) {
	int n = sz(a);
	vii vals;
	forn(i, n) {
		vals.eb(a[i], i);
	}

	sort(all(vals));
	int mx = 0;
	forn(i, n) {
		maxeq(mx, vals[i].S - i);
	}
	return mx;
}


void solve() {
	int n, q;
	cin >> n >> q;
	vi a(n);
	forn(i, n)
		cin >> a[i];

	forn(_, q) {
		int x, v;
		cin >> x >> v;
		a[x] = v;
		cout << solve_lin(a) << '\n';
	}
}

vi countScans(vi a, vi x, vi v) {
	int n = sz(a);
	vi ans(n);
	forn(i, n) {
		a[x[i]] = v[i];
		ans[i] = solve_lin(a);
	}
	return ans;
}


//int main() {
//	ios_base::sync_with_stdio(false);
//	cin.tie(nullptr);
//	cout.tie(nullptr);
//
////	freopen("optmilk.in", "r", stdin);
////	freopen("optmilk.out", "w", stdout);
//
//	int t = 1;
////	cin >> t;
//	while(t--) {
//		solve();
//	}
//}

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