제출 #126569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126569		E869120	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	5755 ms	57400 KiB

bubblesort2

#include "bubblesort2.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class RangeAddMaxSegmentTree {
public:
	vector<int> dat, lazy; int size_ = 1;

	void output() {
		cout << "dat : " << endl;
		for (int i = 1; i <= size_; i *= 2) {
			for (int j = i; j < i * 2; j++) {
				for (int k = 0; k < 5 * ((size_ / i) - 1); k++) cout << " ";
				cout << "[";
				if (dat[j] >= 0 && dat[j] <= 9) cout << "  " << dat[j];
				else if (dat[j] >= -9 && dat[j] <= 99) cout << " " << dat[j];
				else cout << dat[j];
				cout << "]";
				for (int k = 0; k < 5 * ((size_ / i) - 1); k++) cout << " ";
				cout << "     ";
			}
			cout << endl;
		}
		cout << endl;
		cout << "lazy : " << endl;
		for (int i = 1; i <= size_; i *= 2) {
			for (int j = i; j < i * 2; j++) {
				for (int k = 0; k < 5 * ((size_ / i) - 1); k++) cout << " ";
				cout << "[";
				if (lazy[j] >= 0 && lazy[j] <= 9) cout << "  " << lazy[j];
				else if (lazy[j] >= -9 && lazy[j] <= 99) cout << " " << lazy[j];
				else cout << lazy[j];
				cout << "]";
				for (int k = 0; k < 5 * ((size_ / i) - 1); k++) cout << " ";
				cout << "     ";
			}
			cout << endl;
		}
	}
	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2, 0);
		lazy.resize(size_ * 2, 0);
	}
	void push(int pos) {
		if (pos < size_) {
			lazy[pos * 2 + 0] += lazy[pos];
			lazy[pos * 2 + 1] += lazy[pos];
			dat[pos] = max(dat[pos * 2] + lazy[pos * 2], dat[pos * 2 + 1] + lazy[pos * 2 + 1]);
			lazy[pos] = 0;
		}
		else {
			dat[pos] += lazy[pos];
			lazy[pos] = 0;
		}
	}
	void add_(int l, int r, int x, int a, int b, int u) {
		push(u);
		if (l <= a && b <= r) {
			lazy[u] += x;
			push(u);
			return;
		}
		if (r <= a || b <= l) return;

		add_(l, r, x, a, (a + b) >> 1, u * 2);
		add_(l, r, x, (a + b) >> 1, b, u * 2 + 1);
		push(u);
	}
	void add(int l, int r, int x) {
		add_(l, r, x, 0, size_, 1);
	}
	int query_(int l, int r, int a, int b, int u) {
		push(u);
		if (l <= a && b <= r) return dat[u];
		if (r <= a || b <= l) return -(1 << 30);

		int v1 = query_(l, r, a, (a + b) >> 1, u * 2);
		int v2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return max(v1, v2);
	}
	int query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

class RangeAddMaxSegmentTree2 {
public:
	vector<int> dat;

	void output() {
		for (int i = 0; i < dat.size(); i++) printf("% 4d", dat[i]); cout << endl;
	}
	void init(int sz) {
		dat.resize(sz + 2, 0);
	}
	void add(int l, int r, int x) {
		for (int i = l; i < r; i++) dat[i] += x;
	}
	int query(int l, int r) {
		int maxn = -(1 << 30);
		for (int i = l; i < r; i++) maxn = max(maxn, dat[i]);
		return maxn;
	}
};

class BIT {
public:
	vector<int> bit; int size_ = 1;

	void init(int sz) {
		size_ = sz + 2;
		bit.resize(size_ + 2, 0);
	}
	void add(int pos, int x) {
		pos++;
		while (pos <= size_) {
			bit[pos] += x;
			pos += (pos&-pos);
		}
	}
	int sum(int pos) {
		pos++; int s = 0;
		while (pos >= 1) {
			s += bit[pos];
			pos -= (pos&-pos);
		}
		return s;
	}
};

const int INF = 9;
int N, Q; vector<pair<int, int>> G;
RangeAddMaxSegmentTree Z; BIT Y;

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
	N = A.size(); Q = X.size();
	for (int i = 0; i < N; i++) G.push_back(make_pair(A[i], i));
	for (int i = 0; i < Q; i++) G.push_back(make_pair(V[i], X[i]));
	sort(G.begin(), G.end());

	Z.init(G.size() + 2); Y.init(G.size() + 2);
	for (int i = 0; i < G.size(); i++) {
		Z.add(i, i + 1, -INF - Z.query(i, i + 1));
	}
	for (int i = 0; i < N; i++) {
		int pos1 = lower_bound(G.begin(), G.end(), make_pair(A[i], i)) - G.begin();
		Y.add(pos1, 1);
	}
	for (int i = 0; i < N; i++) {
		int pos1 = lower_bound(G.begin(), G.end(), make_pair(A[i], i)) - G.begin();
		int val = i - Y.sum(pos1 - 1);
		Z.add(pos1, pos1 + 1, val - Z.query(pos1, pos1 + 1));
	}
	//Z.output();

	vector<int>ans;

	for (int i = 0; i < Q; i++) {
		int pos1 = lower_bound(G.begin(), G.end(), make_pair(A[X[i]], X[i])) - G.begin();
		int pos2 = lower_bound(G.begin(), G.end(), make_pair(V[i], X[i])) - G.begin();
		Z.add(pos1, pos1 + 1, -INF - Z.query(pos1, pos1 + 1)); Y.add(pos1, -1);
		int val = X[i] - Y.sum(pos2 - 1);
		Z.add(pos2, pos2 + 1, val - Z.query(pos2, pos2 + 1)); Y.add(pos2, 1);

		//Z.output();

		if (pos1 < pos2) Z.add(pos1 + 1, pos2, 1);
		else Z.add(pos2 + 1, pos1, -1);
		//Z.output();
		ans.push_back(Z.query(0, G.size() + 1));
		A[X[i]] = V[i];
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

bubblesort2.cpp: In member function 'void RangeAddMaxSegmentTree2::output()':
bubblesort2.cpp:94:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < dat.size(); i++) printf("% 4d", dat[i]); cout << endl;
                   ~~^~~~~~~~~~~~
bubblesort2.cpp:94:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < dat.size(); i++) printf("% 4d", dat[i]); cout << endl;
   ^~~
bubblesort2.cpp:94:64: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < dat.size(); i++) printf("% 4d", dat[i]); cout << endl;
                                                                ^~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:145:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G.size(); i++) {
                  ~~^~~~~~~~~~

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