Submission #102590

#	Time	Username	Problem	Language	Result	Execution time	Memory
102590		DrumpfTheGodEmperor	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2696 ms	58844 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 5e5 + 5;
int n, q;
struct Query {
	int val, pos, id;
	bool operator<(const Query &rhs) const {
		if (val == rhs.val) {
			if (pos == rhs.pos) return id < rhs.id;
			return pos < rhs.pos;
		}
		return val < rhs.val;
	}
};
vector<Query> vec;
class SegTree {
private:
	int mx[N << 3], cnt[N << 3], lazy[N << 3];
	//cnt saves if a query is "active"
	void build(int l, int r, int x) {
		if (l == r) {
			cnt[x] = 0;
			mx[x] = -inf;
			lazy[x] = 0;
			return;
		}
		int m = (l + r) >> 1;
		build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
		cnt[x] = 0, mx[x] = -inf, lazy[x] = 0;
	}
	void push(int l, int r, int x) {
		mx[x] += lazy[x];
		if (l != r) {
			lazy[x << 1] += lazy[x];
			lazy[x << 1 | 1] += lazy[x];
		}
		lazy[x] = 0;
	}
	void add(int l, int r, int s, int e, int x, int val) {
		push(l, r, x);
		if (l > e || r < s) return;
		if (s <= l && r <= e) {
			lazy[x] += val;
			push(l, r, x);
			return;
		}
		int m = (l + r) >> 1;
		add(l, m, s, e, x << 1, val), add(m + 1, r, s, e, x << 1 | 1, val);
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}
	void set(int l, int r, int pos, int mxval, int cntval, int x) {
		push(l, r, x);
		if (l > pos || r < pos) return;
		if (l == r) {
			mx[x] = mxval;
			cnt[x] = cntval;
			return;
		}
		int m = (l + r) >> 1;
		set(l, m, pos, mxval, cntval, x << 1), set(m + 1, r, pos, mxval, cntval, x << 1 | 1);
		cnt[x] = cnt[x << 1] + cnt[x << 1 | 1];
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}
	int get(int l, int r, int s, int e, int x) {
		push(l, r, x);
		if (l > e || r < s) return 0;
		if (s <= l && r <= e) return cnt[x];
		int m = (l + r) >> 1;
		return get(l, m, s, e, x << 1) + get(m + 1, r, s, e, x << 1 | 1);
	}
public:
	int n;
	void init(int _n) { n = _n; build(0, n - 1, 1); }
	void add(int l, int r, int val) { add(0, n - 1, l, r, 1, val); }
	int get(int l, int r) { return get(0, n - 1, l, r, 1); }
	void set(int pos, int mxval, int cntval) { set(0, n - 1, pos, mxval, cntval, 1); }
	int getans() { return mx[1]; }
} st;
int curid[N], realpos[N];
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
	n = a.size(), q = x.size();
	fw (i, 0, n) vec.pb({a[i], i, i});
	fw (i, 0, q) vec.pb({v[i], x[i], i + n});
	//Save segment tree of queries and the answer for the modified index within the query
	sort(vec.begin(), vec.end());
	st.init(n + q);
	fw (i, 0, vec.size()) {
		int pos = vec[i].pos, id = vec[i].id;
		if (id >= n) realpos[id - n] = i;
		else {
			int tmp = pos - st.get(0, i);
			curid[pos] = i;
			st.set(i, tmp, 1);
			//Don't need to lazy since queries are processed in order here
		}
	}
	vector<int> res;
	fw (i, 0, q) {
		st.add(curid[x[i]], n + q - 1, 1);
		st.set(curid[x[i]], -inf, 0);
		curid[x[i]] = realpos[i];
		int tmp = x[i] - st.get(0, realpos[i]);
		st.add(curid[x[i]], n + q - 1, -1);
		st.set(curid[x[i]], tmp, 1);
		res.pb(st.getans());
	}
	return res;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:11:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fw(i, l, r) for (int i = l; i < r; i++)
bubblesort2.cpp:100:6:
  fw (i, 0, vec.size()) {
      ~~~~~~~~~~~~~~~~                  
bubblesort2.cpp:100:2: note: in expansion of macro 'fw'
  fw (i, 0, vec.size()) {
  ^~

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