148. 달리기

백준

1. python

import heapq

n = int(input())

speed = []
result = []

for _ in range(n):
  r = int(input())
  heapq.heappush(speed, (-r, r))
  heapq.heapify(speed)
  print(speed)
  if len(speed) == 1:
    result.append(1)
  else:
    for i in range(len(speed)):
      if speed[i][1] == r:
        result.append(i + 1)
        

    

for i in range(n):
  print(result[i])

  

왜 계속 -7이 앞으로 들어가는지 모르겠다... :(

시간초과가 떠서 알아보니 이는 세그먼트 트리로 풀어야 되는 문제였다.

2. c++

참고

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef pair<int, int> pii;
 
bool comp(const pii &a, const pii &b)
{
    return a.second < b.second;
}
 
void update(vector<int> &tree, int node, int start, int end, int idx)
{
    if (!(start <= idx && idx <= end))
        return ;
 
    tree[node] += 1;
 
    if (start != end)
    {
        int mid = (start + end) / 2;
        update(tree, node * 2, start, mid, idx);
        update(tree, node * 2 + 1, mid + 1, end, idx);
    }
 
}
int query(vector<int> &tree, int node, int start, int end, int left, int right)
{
    if (start > right || end < left)
        return 0;
    
    if (left <= start && end <= right)
        return tree[node];
 
    int mid = (start + end) / 2;
 
    return query(tree, node * 2, start, mid, left, right) + query(tree, node * 2 + 1, mid + 1, end, left, right);
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    int h = (int)ceil(log2(500000));
    int tree_size = 1 << (1 + h);
 
    vector<pii> arr;
    vector<int> tree(tree_size);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
        arr.push_back({ val, i });
    }
 
    sort(arr.begin(), arr.end());
 
    // 좌표 압축
    for (int i = 0; i < n; i++)
        arr[i].first = i;
 
    sort(arr.begin(), arr.end(), comp);
 
    for (int i = 0; i < n; i++)
    {
        int ans = i - query(tree, 1, 0, 500000, 0, arr[i].first) + 1;
        printf("%d\n", ans);
 
        update(tree, 1, 0, 500000, arr[i].first);
    }
    return 0;
}


출처: https://www.crocus.co.kr/987 [Crocus]

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int, int> pii;

int n, num;
pii player[500000];
int tr[1<<20];

int seg_sum(int node, int s, int e, int l, int r) {
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) {
        //return node; 틀림
        return tr[node];
    }
    else {
        return seg_sum(node * 2, s, (s + e) / 2, l, r) + seg_sum(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
    }
}

void update(int node, int s, int e, int idx, int v) {
    if (idx < s || e < idx) return;
    if (s == e) {
        tr[node] = v;
        /*
        tr[node] += v;
        tr[node] -= v;
        tr[node] ^= v;
        tr[node] *= v;
        tr[node] &= v;
        */
    }
    else {
        update(node * 2, s, (s + e) / 2, idx, v);
        update(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
        tr[node] = tr[node * 2] + tr[node * 2 + 1];
    }
}

bool comp(pii p1, pii p2) {
    return p1.second < p2.second;
}

int main() {
    freopen("res/B2517.in", "r", stdin);
    scanf("%d", &n);
    for (int i = 0 ; i < n ; i++) {
        int power;
        scanf("%d", &power);
        player[i].first = i;
        player[i].second = power;
    }
    // sort power --> relabeling 
    sort(player, player + n, comp);

    for (int i = 0 ; i < n ; i++) {
        player[i].second = ++num;   // i + 1
    }

    // sort original order
    sort(player, player + n);
    for (int i = 0 ; i < n ; i++) {
        int curpower = player[i].second;
        int cnt = 0;
        if (curpower > 1) {
            cnt = seg_sum(1, 1, num, 1, curpower - 1);
        }
        update(1, 1, num, curpower, 1);
        printf("%d\n", i + 1 - cnt);
    }
}