Submission #398728

#	Time	Username	Problem	Language	Result	Execution time	Memory
398728		nikatamliani	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	3744 ms	111248 KiB

bubblesort2

#include "bits/stdc++.h"
#include "bubblesort2.h"
using namespace std;
template <typename T>
struct segment_tree {
	vector<T> tree;
	vector<T> lazy;
	T neutral;
	function<T(T, T)> join;
	int size;
	segment_tree() {}
	segment_tree(int _size, T _neutral, function<T(T, T)> f) {
		join = f;
		size = _size;
		neutral = _neutral;
		tree = vector<T>(4 * size, neutral);
		lazy = vector<T>(4 * size);
	}
	
	void prop(int l, int r, int p) {
		if(lazy[p] == 0) return;
		if(l < r) {
			lazy[p << 1] += lazy[p];
			lazy[p << 1 | 1] += lazy[p];
		}
		tree[p] += lazy[p];
		lazy[p] = 0;
	}
	
	void point_update(int id, T val) {
		point_update(1, size, id, val, 1); 
	}
	
	void point_update(int l, int r, int x, T val, int p) {
		prop(l, r, p);
		if(l > x || r < x) {
			return;
		}
		if(l == r) {
			tree[p] = val;
			return;
		}
		int middle = l + r >> 1;
		point_update(l, middle, x, val, p << 1);
		point_update(middle+1, r, x, val, p << 1 | 1);
		tree[p] = join(tree[p << 1], tree[p << 1 | 1]);
	}
	
	void range_add(int L, int R, T val) {
		if(L > R) {
			return;
		}
		range_add(1, size, L, R, val, 1);
	}
	
	void range_add(int l, int r, int L, int R, T val, int p) {
		prop(l, r, p);
		if(L > r || l > R) return;
		if(L <= l && R >= r) {
			lazy[p] += val;
			prop(l, r, p);
			return;
		}
		int middle = l + r >> 1; 
		range_add(l, middle, L, R, val, p << 1);
		range_add(middle+1, r, L, R, val, p << 1 | 1); 
		tree[p] = join(tree[p << 1], tree[p << 1 |1]);
	}
	
	T get(int id) {
		return query(id, id);
	}
	
	T query(int L, int R) {
		if(L > R) {
			return neutral;
		}
		return query(1, size, L, R, 1); 
	}
	
	T query(int l, int r, int L, int R, int p) {
		prop(l, r, p); 
		if(L > r || l > R) return neutral;
		if(L <= l && R >= r) return tree[p];
		int middle = l + r >> 1;
		T lft = query(l, middle, L, R, p << 1);
		T rgh = query(middle+1, r, L, R, p << 1 | 1);
		return join(lft, rgh);
	}
};
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	int Q = (int)X.size(), N = (int)A.size();
	vector<int> answer(Q);
	vector<array<int, 4>> coords;
	for(int i = 0; i < N; ++i) {
		coords.push_back({A[i], i, i, 0});
	}
	for(int i = 0; i < Q; ++i) {
		coords.push_back({V[i], X[i], i, 1});
	}
	sort(coords.begin(), coords.end());
	for(int i = 0; i < (int)coords.size(); ++i) {
		if(coords[i][3] == 0) {
			A[coords[i][2]] = i+1;
		} else {
			V[coords[i][2]] = i+1;
		}
	}
	segment_tree<int> t(N + Q, -1e9, [](int x, int y) -> int {
		return x > y ? x : y;
	});
	segment_tree<int> bruh(N + Q, 0, [](int x, int y) -> int {
		return x+y;
	});
	vector<int> id(N + Q + 1);
	for(int i = 0; i < N; ++i) {
		id[A[i]] = i;
	}
	vector<int> save_A = A;
	sort(A.begin(), A.end());
	for(int i = 0; i < N; ++i) {
		t.point_update(A[i], id[A[i]] - i);
		bruh.point_update(A[i], 1); 
	}
	A = save_A;
	for(int i = 0; i < Q; ++i) {
		int prv = A[X[i]];
		int nxt = V[i];
		A[X[i]] = V[i];
		id[nxt] = id[prv];
		bruh.point_update(prv, 0);
		bruh.point_update(nxt, 1);
		if(nxt > prv) {
			t.range_add(prv, nxt, 1);
			t.point_update(nxt, id[nxt] - bruh.query(1, nxt-1));
		} else {
			t.range_add(nxt, prv, -1);
			t.point_update(nxt, id[nxt] - bruh.query(1, nxt-1));
		}
		t.point_update(prv, -1e9);
		answer[i] = t.query(1, N + Q);
	}
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In instantiation of 'void segment_tree<T>::point_update(int, int, int, T, int) [with T = int]':
bubblesort2.cpp:31:3:   required from 'void segment_tree<T>::point_update(int, T) [with T = int]'
bubblesort2.cpp:122:36:   required from here
bubblesort2.cpp:43:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int middle = l + r >> 1;
      |                ~~^~~
bubblesort2.cpp: In instantiation of 'void segment_tree<T>::range_add(int, int, int, int, T, int) [with T = int]':
bubblesort2.cpp:53:3:   required from 'void segment_tree<T>::range_add(int, int, T) [with T = int]'
bubblesort2.cpp:134:27:   required from here
bubblesort2.cpp:64:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   int middle = l + r >> 1;
      |                ~~^~~
bubblesort2.cpp: In instantiation of 'T segment_tree<T>::query(int, int, int, int, int) [with T = int]':
bubblesort2.cpp:78:32:   required from 'T segment_tree<T>::query(int, int) [with T = int]'
bubblesort2.cpp:135:53:   required from here
bubblesort2.cpp:85:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |   int middle = l + r >> 1;
      |                ~~^~~

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