Submission #367317

#	Time	Username	Problem	Language	Result	Execution time	Memory
367317		cheissmart	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	156 ms	52860 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e6 + 7;

struct node {
	int mx, add, lz;
	node(int x = 0) {
		mx = x;
		add = lz = 0;		
	}
} t[N * 4];

int n;

void apply(int v, int x) {
	t[v].mx += x;
	t[v].add += x;
	t[v].lz += x;
}

void push(int v) {
	apply(v * 2, t[v].lz);
	apply(v * 2 + 1, t[v].lz);
	t[v].lz = 0;
}

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

void build(int v = 1, int tl = 0, int tr = n) {
	if(tr - tl == 1) {
		t[v] = node(-INF);
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm);
	build(v * 2 + 1, tm, tr);
	pull(v);
}

void add(int l, int r, int x, int v = 1, int tl = 0, int tr = n) {
	if(l <= tl && tr <= r) {
		apply(v, x);
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	if(l < tm) add(l, r, x, v * 2, tl, tm);
	if(r > tm) add(l, r, x, v * 2 + 1, tm, tr);
	pull(v);
}

void set_val(int pos, int x, int v = 1, int tl = 0, int tr = n) {
	if(tr - tl == 1) {
		t[v] = node(x);
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	if(pos < tm) set_val(pos, x, v * 2, tl, tm);
	else set_val(pos, x, v * 2 + 1, tm, tr);
	pull(v);
}

int get_add(int pos, int v = 1, int tl = 0, int tr = n) {
	if(tr - tl == 1)
		return t[v].add;
	push(v);
	int tm = (tl + tr) / 2;
	if(pos < tm) return get_add(pos, v * 2, tl, tm);
	else return get_add(pos, v * 2 + 1, tm, tr);
}

vi countScans(vi A, vi X, vi Y) {
	int Q = X.size(), N = A.size();
	V<pi> v;
	for(int i = 0; i < N; i++) v.EB(A[i], i);
	for(int i = 0; i < Q; i++) v.EB(Y[i], X[i]);
	map<pi, int> id;
	sort(ALL(v));
	v.resize(unique(ALL(v)) - v.begin());
	for(int i = 0; i < v.size(); i++)
		id[v[i]] = i;
	n = v.size();
	build();
	for(int i = 0; i < N; i++) {
		int x = id[{A[i], i}];
		A[i] = x;
		set_val(x, i);
	}
	for(int i = 0; i < N; i++)
		if(A[i] + 1 < n)
			add(A[i] + 1, n, -1);
	vi ans(Q);
	for(int i = 0; i < Q; i++) {
		int pos = X[i], val = Y[i], old_val = A[pos];
		val = id[{val, pos}];
		A[pos] = val;
		// old_val -> val
		if(old_val + 1 < n)
			add(old_val + 1, n, 1);
		set_val(old_val, -INF);
		int added = get_add(val);
		set_val(val, added + pos);
		if(val + 1 < n)
			add(val + 1, n, -1);
		ans[i] = t[1].mx;
	}
	return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'vi countScans(vi, vi, vi)':
bubblesort2.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int i = 0; i < v.size(); i++)
      |                 ~~^~~~~~~~~~

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