oj.uz

답안 #126568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126568 2019-07-08T06:03:53 Z E869120 Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 9000 ms 12048 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 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;
RangeAddMaxSegmentTree2 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;
}

Compilation message

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.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 13 ms 504 KB Output is correct
4 Correct 13 ms 632 KB Output is correct
5 Correct 13 ms 504 KB Output is correct
6 Correct 12 ms 632 KB Output is correct
7 Correct 13 ms 504 KB Output is correct
8 Correct 13 ms 556 KB Output is correct
9 Correct 13 ms 504 KB Output is correct
10 Correct 14 ms 632 KB Output is correct
11 Correct 13 ms 504 KB Output is correct
12 Correct 13 ms 504 KB Output is correct
13 Correct 13 ms 504 KB Output is correct
14 Correct 14 ms 504 KB Output is correct
15 Correct 14 ms 508 KB Output is correct
16 Correct 14 ms 504 KB Output is correct
17 Correct 15 ms 504 KB Output is correct
18 Correct 14 ms 500 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 13 ms 504 KB Output is correct
4 Correct 13 ms 632 KB Output is correct
5 Correct 13 ms 504 KB Output is correct
6 Correct 12 ms 632 KB Output is correct
7 Correct 13 ms 504 KB Output is correct
8 Correct 13 ms 556 KB Output is correct
9 Correct 13 ms 504 KB Output is correct
10 Correct 14 ms 632 KB Output is correct
11 Correct 13 ms 504 KB Output is correct
12 Correct 13 ms 504 KB Output is correct
13 Correct 13 ms 504 KB Output is correct
14 Correct 14 ms 504 KB Output is correct
15 Correct 14 ms 508 KB Output is correct
16 Correct 14 ms 504 KB Output is correct
17 Correct 15 ms 504 KB Output is correct
18 Correct 14 ms 500 KB Output is correct
19 Correct 117 ms 988 KB Output is correct
20 Correct 152 ms 1044 KB Output is correct
21 Correct 141 ms 1016 KB Output is correct
22 Correct 147 ms 1188 KB Output is correct
23 Correct 152 ms 1004 KB Output is correct
24 Correct 152 ms 1036 KB Output is correct
25 Correct 157 ms 1016 KB Output is correct
26 Correct 157 ms 1016 KB Output is correct
27 Correct 162 ms 1152 KB Output is correct
28 Correct 162 ms 1016 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 1140 KB Output is correct
2 Correct 1748 ms 2704 KB Output is correct
3 Correct 5537 ms 4332 KB Output is correct
4 Correct 5537 ms 4304 KB Output is correct
5 Correct 5304 ms 4388 KB Output is correct
6 Correct 5335 ms 4164 KB Output is correct
7 Correct 5200 ms 4264 KB Output is correct
8 Correct 5216 ms 3788 KB Output is correct
9 Correct 5218 ms 3796 KB Output is correct
10 Correct 4667 ms 3600 KB Output is correct
11 Correct 4688 ms 3708 KB Output is correct
12 Correct 4664 ms 3744 KB Output is correct
13 Correct 4821 ms 3956 KB Output is correct
14 Correct 4818 ms 4260 KB Output is correct
15 Correct 4819 ms 4180 KB Output is correct
16 Correct 4993 ms 4312 KB Output is correct
17 Correct 4969 ms 4276 KB Output is correct
18 Correct 4969 ms 4196 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 13 ms 504 KB Output is correct
4 Correct 13 ms 632 KB Output is correct
5 Correct 13 ms 504 KB Output is correct
6 Correct 12 ms 632 KB Output is correct
7 Correct 13 ms 504 KB Output is correct
8 Correct 13 ms 556 KB Output is correct
9 Correct 13 ms 504 KB Output is correct
10 Correct 14 ms 632 KB Output is correct
11 Correct 13 ms 504 KB Output is correct
12 Correct 13 ms 504 KB Output is correct
13 Correct 13 ms 504 KB Output is correct
14 Correct 14 ms 504 KB Output is correct
15 Correct 14 ms 508 KB Output is correct
16 Correct 14 ms 504 KB Output is correct
17 Correct 15 ms 504 KB Output is correct
18 Correct 14 ms 500 KB Output is correct
19 Correct 117 ms 988 KB Output is correct
20 Correct 152 ms 1044 KB Output is correct
21 Correct 141 ms 1016 KB Output is correct
22 Correct 147 ms 1188 KB Output is correct
23 Correct 152 ms 1004 KB Output is correct
24 Correct 152 ms 1036 KB Output is correct
25 Correct 157 ms 1016 KB Output is correct
26 Correct 157 ms 1016 KB Output is correct
27 Correct 162 ms 1152 KB Output is correct
28 Correct 162 ms 1016 KB Output is correct
29 Correct 89 ms 1140 KB Output is correct
30 Correct 1748 ms 2704 KB Output is correct
31 Correct 5537 ms 4332 KB Output is correct
32 Correct 5537 ms 4304 KB Output is correct
33 Correct 5304 ms 4388 KB Output is correct
34 Correct 5335 ms 4164 KB Output is correct
35 Correct 5200 ms 4264 KB Output is correct
36 Correct 5216 ms 3788 KB Output is correct
37 Correct 5218 ms 3796 KB Output is correct
38 Correct 4667 ms 3600 KB Output is correct
39 Correct 4688 ms 3708 KB Output is correct
40 Correct 4664 ms 3744 KB Output is correct
41 Correct 4821 ms 3956 KB Output is correct
42 Correct 4818 ms 4260 KB Output is correct
43 Correct 4819 ms 4180 KB Output is correct
44 Correct 4993 ms 4312 KB Output is correct
45 Correct 4969 ms 4276 KB Output is correct
46 Correct 4969 ms 4196 KB Output is correct
47 Execution timed out 9074 ms 12048 KB Time limit exceeded
48 Halted 0 ms 0 KB -