글 읽기 - 참조자를 사용하는 것과 사용하지 않을 때 시간차이가 왜 나는 건가요?

math_rabbit_1028 3년 전 0

참조자를 사용하지 않을 때는 시간초과를 받았고 참조자를 사용하니 시간초과를 받지 않았습니다.

왜 이런 차이가 발생하는 건가요?

// 시간 초과 없음
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;

int init_min(vector<int> &min_tree, vector<int> &arr, int idx, int s, int e) {
    if (s == e) return min_tree[idx] = arr[s];
    else {
        return min_tree[idx] = min(init_min(min_tree, arr, idx * 2, s, (s + e) / 2), 
            init_min(min_tree, arr, idx * 2 + 1, (s + e) / 2 + 1, e));
    }
}

int init_max(vector<int> &max_tree, vector<int> &arr, int idx, int s, int e) {
    if (s == e) return max_tree[idx] = arr[s];
    else {
        return max_tree[idx] = max(init_max(max_tree, arr, idx * 2, s, (s + e) / 2), 
            init_max(max_tree, arr, idx * 2 + 1, (s + e) / 2 + 1, e));
    }
}

int ans_min(vector<int> &min_tree, int idx, int s, int e, int p, int q) {
    if (q < s || e < p) return 2147000000;
    else if (p <= s && e <= q) return min_tree[idx];
    else {
        return min(ans_min(min_tree, idx * 2, s, (s + e) / 2, p, q), 
            ans_min(min_tree, idx * 2 + 1, (s + e) / 2 + 1, e, p, q));
    }
}

int ans_max(vector<int> &max_tree, int idx, int s, int e, int p, int q) {
    if (q < s || e < p) return 0;
    else if (p <= s && e <= q) return max_tree[idx];
    else {
        return max(ans_max(max_tree, idx * 2, s, (s + e) / 2, p, q), 
            ans_max(max_tree, idx * 2 + 1, (s + e) / 2 + 1, e, p, q));
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    vector<int> arr(n), min_tree(4 * n), max_tree(4 * n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    init_min(min_tree, arr, 1, 0, n - 1);
    init_max(max_tree, arr, 1, 0, n - 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        cout << ans_min(min_tree, 1, 0, n - 1, a, b) << " " << ans_max(max_tree, 1, 0, n - 1, a, b) << "\n";
    }
    return 0;
}


// 시간 초과
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;

int init_min(vector<int> &min_tree, vector<int> arr, int idx, int s, int e) {
    if (s == e) return min_tree[idx] = arr[s];
    else {
        return min_tree[idx] = min(init_min(min_tree, arr, idx * 2, s, (s + e) / 2), 
            init_min(min_tree, arr, idx * 2 + 1, (s + e) / 2 + 1, e));
    }
}

int init_max(vector<int> &max_tree, vector<int> arr, int idx, int s, int e) {
    if (s == e) return max_tree[idx] = arr[s];
    else {
        return max_tree[idx] = max(init_max(max_tree, arr, idx * 2, s, (s + e) / 2), 
            init_max(max_tree, arr, idx * 2 + 1, (s + e) / 2 + 1, e));
    }
}

int ans_min(vector<int> min_tree, int idx, int s, int e, int p, int q) {
    if (q < s || e < p) return 2147000000;
    else if (p <= s && e <= q) return min_tree[idx];
    else {
        return min(ans_min(min_tree, idx * 2, s, (s + e) / 2, p, q), 
            ans_min(min_tree, idx * 2 + 1, (s + e) / 2 + 1, e, p, q));
    }
}

int ans_max(vector<int> max_tree, int idx, int s, int e, int p, int q) {
    if (q < s || e < p) return 0;
    else if (p <= s && e <= q) return max_tree[idx];
    else {
        return max(ans_max(max_tree, idx * 2, s, (s + e) / 2, p, q), 
            ans_max(max_tree, idx * 2 + 1, (s + e) / 2 + 1, e, p, q));
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    vector<int> arr(n), min_tree(4 * n), max_tree(4 * n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    init_min(min_tree, arr, 1, 0, n - 1);
    init_max(max_tree, arr, 1, 0, n - 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        cout << ans_min(min_tree, 1, 0, n - 1, a, b) << " " << ans_max(max_tree, 1, 0, n - 1, a, b) << "\n";
    }
    return 0;
}

bupjae 3년 전 1

vector 인자에 참조자가 없으면 함수 호출을 할 때 마다 vector 내용 전체를 복사합니다.

math_rabbit_1028 3년 전 0

@bupjae 아 그렇군요 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

참조자를 사용하는 것과 사용하지 않을 때 시간차이가 왜 나는 건가요?

math_rabbit_1028 3년 전 0

bupjae 3년 전 1

math_rabbit_1028 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말