Submission #520033

#	Time	Username	Problem	Language	Result	Execution time	Memory
520033		akhan42	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	9091 ms	46440 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<ii, null_type, less<ii>, 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;


struct Seg {
	int n;
	vi add, mx;

	Seg(int n, vi &vals): n(n) {
		add.assign(4 * n, 0);
		mx.assign(4 * n, 0);

		build(vals);
	}

	void propagate(int v, int tl, int tr) {
		if(tl == tr || add[v] == 0)
			return;

		add[2 * v] += add[v];
		add[2 * v + 1] += add[v];
		mx[2 * v] += add[v];
		mx[2 * v + 1] += add[v];
		add[v] = 0;
	}

	void pull(int v) {
		mx[v] = max(mx[2 * v], mx[2 * v + 1]);
	}

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

		if(tl == tr) {
			mx[v] = vals[tl];
			return;
		}
		int tm = (tl + tr) / 2;

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

		pull(v);
	}

	void update(int l, int r, int val, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;
		propagate(v, tl, tr);
		if(l > r) return;

		if(tl == l && r == tr) {
			add[v] = val;
			mx[v] += val;
			return;
		}
		int tm = (tl + tr) / 2;

		update(l, min(r, tm), val, 2 * v, tl, tm);
		update(max(l, tm + 1), r, val, 2 * v + 1, tm + 1, tr);

		pull(v);
	}

	int query(int l, int r, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;
		propagate(v, tl, tr);
		if(l > r) return -INF;

		if(tl == l && r == tr)
			return mx[v];
		int tm = (tl + tr) / 2;

		int ql = query(l, min(r, tm), 2 * v, tl, tm);
		int qr = query(max(l, tm + 1), r, 2 * v + 1, tm + 1, tr);

		return max(ql, qr);
	}

	int get_max() {
		return query(0, n - 1);
	}

	int at(int p) {
		return query(p, p);
	}

	void set(int p, int nval) {
		update(p, p, nval - at(p));
	}
};


struct Seg2 {
	int n;
	vi t;

	Seg2(int n): n(n) {
		t.resize(2 * n);
	}

	void set(int p, int val) {
		for(t[p += n] = val; p > 1; p /= 2)
			t[p >> 1] = t[p] + t[p ^ 1];
	}

	int sum(int l, int r) {
		int res = 0;
		for(l += n, r += n + 1; l < r; l /= 2, r /= 2) {
			if(l & 1) res += t[l++];
			if(r & 1) res += t[--r];
		}
		return res;
	}

	int at(int p) {
		return sum(0, p) - sum(0, p - 1);
	}
};


struct SegSim {
	int n;
	vi t;

	SegSim(int n, vi &vals): n(n) {
		t.resize(n);
		forn(i, n)
			t[i] = vals[i];
	}

	void update(int l, int r, int val) {
		forbn(i, l, r + 1)
			t[i] += val;
	}

	void set(int p, int val) {
		t[p] = val;
	}

	int get_max() {
		int mx = -1000 * 1000 * 1000;
		forn(i, n)
			maxeq(mx, t[i]);
		return mx;
	}
};


vi countScans(vi a, vi xs, vi vs) {
	int n = sz(a);
	int q = sz(xs);

	set<ii> s;
	vii vals;

	forn(i, n) {
		s.insert({a[i], i});
		vals.eb(a[i], i);
	}
	forn(i, q) {
		s.insert({vs[i], xs[i]});
	}
	map<ii, int> p2ind;
	int ct = 0;
	for(ii el: s) {
		p2ind[el] = ct++;
	}

	int N = sz(s);

	sort(all(vals));

	vi seg_vals(N, -INF);
	Seg2 sl(N);

	forn(i, n) {
		int ind = p2ind[vals[i]];
		seg_vals[ind] = vals[i].S - i;
		sl.set(ind, 1);
	}

	SegSim seg(N, seg_vals);
	vi ans(q);

	forn(i, q) {
		int x = xs[i], v = vs[i];

		int ind_fr = p2ind[{a[x], x}];
		int ind_to = p2ind[{v, x}];

		sl.set(ind_fr, 0);
		sl.set(ind_to, 1);

		if(ind_to > ind_fr) {
			seg.update(ind_fr, ind_to, 1);
		}
		if(ind_to < ind_fr) {
			seg.update(ind_to, ind_fr, -1);
		}

		if(ind_to != ind_fr) {
			int rem = x - sl.sum(0, ind_to - 1);
			seg.set(ind_fr, -INF);
			seg.set(ind_to, rem);
		}

		a[x] = v;
		ans[i] = seg.get_max();
//
//		int mx = -1000;
//		forn(x, n) {
//			int ind = p2ind[{a[x], x}];
//			maxeq(mx, x - sl.sum(0, ind - 1));
////			cout << ind << ' ' << sl.sum(0, ind - 1) << endl;
//		}
//		ans[i] = mx;
	}

	return ans;
}


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

	vi xs, vs;
	forn(_, q) {
		int x, v;
		cin >> x >> v;
		xs.pb(x);
		vs.pb(v);
	}

	vi ans = countScans(a, xs, vs);

	for(int a: ans)
		cout << a << endl;

}


//
//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: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 0 / 40