百駿2517号:ランニング
13441 ワード
競走する
百駿2517号:ランニング
アイデア
自分より実力の高い人を何人か探せばいい.しかし、実力の最高価格は10億ウォンだ.10億サイズの配列を作ると爆発するので、座標圧縮を行います.Nはせいぜい50万だから完全に可能だ座標圧縮は地図で作られています.実力順に並べ替えたら、最小の値から順に0,1,2...
コード#コード#
#include <bits/stdc++.h>
using namespace std;
const int MAX = 500001;
int N;
vector<int> arr, v;
vector<int> tree(MAX*4);
map<int, int> m;
void update(int start, int end, int idx, int node) {
if (idx < start || end < idx) return;
if (start == end) {
tree[node]++;
return;
}
update(start, (start+end)/2, idx, node*2);
update((start+end)/2+1, end, idx, node*2+1);
tree[node] = tree[node*2] + tree[node*2+1];
}
int query(int start, int end, int left, int right, int node) {
if (end < left || right < start) 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);
}
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);
v.push_back(x);
}
sort(arr.begin(), arr.end());
for (int i = 0; i < N; i++) {
m[arr[i]] = i;
}
for (int i = 0; i < N; i++) {
cout << query(0, N-1, m[v[i]], N-1, 1)+1 << '\n';
update(0, N-1, m[v[i]], 1);
}
return 0;
}
おしゃべり
なんとか通過しました.他の人が解く様子を見て、pairで1つは実力で、1つは圧縮された座標という方法で時間の複雑さを減らします.後で時間制限があればそうします
Reference
この問題について(百駿2517号:ランニング), 我々は、より多くの情報をここで見つけました
https://velog.io/@ks1ksi/백준-2517번-달리기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <bits/stdc++.h>
using namespace std;
const int MAX = 500001;
int N;
vector<int> arr, v;
vector<int> tree(MAX*4);
map<int, int> m;
void update(int start, int end, int idx, int node) {
if (idx < start || end < idx) return;
if (start == end) {
tree[node]++;
return;
}
update(start, (start+end)/2, idx, node*2);
update((start+end)/2+1, end, idx, node*2+1);
tree[node] = tree[node*2] + tree[node*2+1];
}
int query(int start, int end, int left, int right, int node) {
if (end < left || right < start) 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);
}
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);
v.push_back(x);
}
sort(arr.begin(), arr.end());
for (int i = 0; i < N; i++) {
m[arr[i]] = i;
}
for (int i = 0; i < N; i++) {
cout << query(0, N-1, m[v[i]], N-1, 1)+1 << '\n';
update(0, N-1, m[v[i]], 1);
}
return 0;
}
Reference
この問題について(百駿2517号:ランニング), 我々は、より多くの情報をここで見つけました https://velog.io/@ks1ksi/백준-2517번-달리기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol