oj.uz

답안 #126561

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126561 2019-07-08T05:47:20 Z E869120 Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 73 ms 1600 KB 
#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 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 = (1 << 23);
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(i, i + 1)); Y.add(pos1, -1);
		int val = X[i] - Y.sum(pos2 - 1);
		Z.add(pos2, pos2 + 1, val - Z.query(i, i + 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));
	}
	return ans;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:125:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G.size(); i++) {
                  ~~^~~~~~~~~~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

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