白駿3006号:ターボ過給機
18319 ワード
タービン過給機
白駿3006号:ターボ過給機
アイデア
以前のBubble Sotの問題では,クエリの順序を変えるだけで解決できる.
0~iとN-1-i~N-1ラウンド流刑なら1 N 2 N-1の順に並べられます
コード#コード#
#include <bits/stdc++.h>
using namespace std;
int N;
vector<pair<int, int>> arr;
vector<int> tree;
int init(int start, int end, int node) {
if (start == end) return tree[node] = 1;
return tree[node] = init(start, (start+end)/2, node*2) + init((start+end)/2+1, end, node*2+1);
}
int query(int start, int end, int left, int right, int node) {
if (right < start || left > end) return 0;
if (left <= start && end <= right) return tree[node];
return query(start, (start+end)/2, left, right, node*2) + query((start+end)/2+1, end, left, right, node*2+1);
}
void update(int start, int end, int idx, int node, int value) {
if (start > idx || end < idx) return;
if (start == end) {
if (start == idx) tree[node] = value;
return;
}
update(start, (start+end)/2, idx, node*2, value);
update((start+end)/2+1, end, idx, node*2+1, value);
tree[node] = tree[node*2] + tree[node*2+1];
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
arr.push_back({x, i});
}
int h = (int)ceil(log2(N));
int size = (1<<h+1);
tree.resize(size);
init(0, N-1, 1);
sort(arr.begin(), arr.end());
for (int i = 0; i < N/2; i++) {
int q = arr[i].second;
int x = query(0, N-1, 0, q, 1)-1;
cout << x << '\n';
update(0, N-1, q, 1, 0);
q = arr[N-1-i].second;
x = query(0, N-1, q, N-1, 1)-1;
cout << x << '\n';
update(0, N-1, q, 1, 0);
}
if (N%2) {
cout << 0;
}
return 0;
}
おしゃべり
ターボ過給機(遅い)
Reference
この問題について(白駿3006号:ターボ過給機), 我々は、より多くの情報をここで見つけました
https://velog.io/@ks1ksi/백준-3006번-터보소트
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <bits/stdc++.h>
using namespace std;
int N;
vector<pair<int, int>> arr;
vector<int> tree;
int init(int start, int end, int node) {
if (start == end) return tree[node] = 1;
return tree[node] = init(start, (start+end)/2, node*2) + init((start+end)/2+1, end, node*2+1);
}
int query(int start, int end, int left, int right, int node) {
if (right < start || left > end) return 0;
if (left <= start && end <= right) return tree[node];
return query(start, (start+end)/2, left, right, node*2) + query((start+end)/2+1, end, left, right, node*2+1);
}
void update(int start, int end, int idx, int node, int value) {
if (start > idx || end < idx) return;
if (start == end) {
if (start == idx) tree[node] = value;
return;
}
update(start, (start+end)/2, idx, node*2, value);
update((start+end)/2+1, end, idx, node*2+1, value);
tree[node] = tree[node*2] + tree[node*2+1];
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
arr.push_back({x, i});
}
int h = (int)ceil(log2(N));
int size = (1<<h+1);
tree.resize(size);
init(0, N-1, 1);
sort(arr.begin(), arr.end());
for (int i = 0; i < N/2; i++) {
int q = arr[i].second;
int x = query(0, N-1, 0, q, 1)-1;
cout << x << '\n';
update(0, N-1, q, 1, 0);
q = arr[N-1-i].second;
x = query(0, N-1, q, N-1, 1)-1;
cout << x << '\n';
update(0, N-1, q, 1, 0);
}
if (N%2) {
cout << 0;
}
return 0;
}
Reference
この問題について(白駿3006号:ターボ過給機), 我々は、より多くの情報をここで見つけました https://velog.io/@ks1ksi/백준-3006번-터보소트テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol