글 읽기 - c++ 시간초과 질문있습니다.

cksgnlcjswo 3년 전 0

hash table을 이용해서 입력받은 번호의 인덱스번호 찾기를 구현했고 세그먼트 트리를 이용했습니다.

통과하신 분들 코드랑 로직은 같다고 생각되는데, 시간초과가 나서 질문드립니다!

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
#define FASTIO ios::sync_with_stdio(false); \
               cin.tie(0);

using namespace std;

long long ans;
int N;

long long query(vector<int> tree, int node, int start, int end, int left, int right) {
    if(start > right || end < left ) return 0;
    if(start >= left && 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);
}

void update(vector<int> &tree, int node, int start,int end,int target) {
    if(start > target || target > end) return;
    if(start == end) {
        tree[node]++;
        return;
    }

    int mid = (start + end) /2;
    update(tree,node*2,start,mid,target);
    update(tree,node*2+1,mid+1,end,target);
    tree[node] = tree[node*2] + tree[node*2+1];
}

int main(void) {
    FASTIO;
    unordered_map<int, int> um;
    cin>>N;

    int h = int(ceil(log2(N)));
    int tree_size = 1<<(1+h);

    vector<int> tree(tree_size);
    
    for(int i=1;i<=N;i++) {
        int tmp;
        cin>>tmp;
        um[tmp] = i; //key는 값 value는 인덱스
    }

    for(int i=1;i<=N;i++) {
        int tmp;
        cin>>tmp;

        int idx = um[tmp]; //몇번 째로 입력됐는지?
        ans += query(tree,1,1,N,idx+1,N); // 0~i-1번째까지중에서 입력됐던 차례 보다 컸던 인덱스 개수
        update(tree,1,1,N,idx);
    }
    cout<<ans;
}

adxx 3년 전 0

저랑 같은 방식이시네요 다만 저는 map을 사용했는데 마찬가지로 TLE를 받습니다....

혹시 해결 하셨는지요?

adxx 3년 전 0

map을 이용하면 왜 TLE인지는 모르겠지만

저는 이분탐색을 통해 이를 해결했습니다

입력받을때 pair를 이용해 값과 인덱스를 묶어주고 이를 정렬하여 찾아주면 됩니다

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

문제

문제

출처

ICPC

c++ 시간초과 질문있습니다.

cksgnlcjswo 3년 전 0

adxx 3년 전 0

adxx 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말