oj.uz

답안 #520019

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520019 2022-01-28T06:48:32 Z akhan42 Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 347 ms 20032 KB 
#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) {
//		cout << "inf loop update " << endl;
		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) {
//		cout << "inf loop query " << endl;
		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));
	}
};


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

	set<ii> s;
	vii vals;
	ordered_set cur_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) {
//		cout << "stopped here 1" << endl;
		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);
//			cout << "stopped here 2" << endl;
		}

		a[x] = v;
		ans[i] = seg.get_max();
//		cout << "stopped here 3" << endl;
	}

//	cout << "stopped here exit" << endl;
	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);
//	cout << "stopped here not yet" << endl;

//	cout << "stopped here 4" << endl;

	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
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 6848 KB Output is correct
2 Correct 177 ms 13376 KB Output is correct
3 Incorrect 347 ms 20032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 452 KB Output isn't correct
2 Halted 0 ms 0 KB -