Submission #520020

#	Time	Username	Problem	Language	Result	Execution time	Memory
520020		akhan42	Bubble Sort 2 (JOI18_bubblesort2)	C++17	Compilation error	0 ms	0 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));
	}
};


ordered_set cur_vals;

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);
		cur_vals.insert(vals.back());
	}
	forn(i, q) {
		s.insert({vs[i], xs[i]});
	}
	map<ii, int> p2ind;
	for(ii el: s) {
		p2ind[el] = sz(p2ind);
	}

	int N = sz(s);

	sort(all(vals));

	vi seg_vals(N, -INF);
	forn(i, n) {
		int ind = p2ind[vals[i]];
		seg_vals[ind] = vals[i].S - i;
	}

	Seg 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}];

		cur_vals.erase({a[x], x});
		cur_vals.insert({v, x});

		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 - cur_vals.order_of_key({v, x});
			seg.set(ind_fr, -INF);
			seg.set(ind_to, rem);
		}

		a[x] = v;
		ans[i] = seg.get_max();
	}

	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();
	}
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccFYXjdY.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3G9IkX.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status