글 읽기 - 9463 (순열그래프). 마지막 큰 데이터 채점중 시간초과가 되버려요

skeksk91 9년 전 0

펜윅트리를 사용하였습니다.

복잡도가 O(n * logn)이고 n최대값이 10^6 인데

채점95%다하고 마지막채점중에 시간초과 나네요 ㅠㅠ

펜윅트리 sum이랑 업데이트하는게 logn 으로 나오는디

제가 공부를 잘못한걸까요 ㅠ 책을 다시봐도 확인이 안되네욤

#include <iostream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

const int maxn = 100000+10;

long long tree[maxn];
int arr[maxn];
int input[maxn];
long long n,sum;

int psum(int pos){
    ++pos;
    if(pos <= 0) return 0;
    long long ret=0;
    
    while(pos>0){
        ret += tree[pos];
        pos &= (pos-1);
    }
    return ret;
}

void add(int pos){
    ++pos;
    while(pos < n){
        tree[pos]++;
        pos += (pos&-pos);
    }
}

int main(){
    int t;
    cin >> t;
    
    while(t--){
        memset(tree,0,sizeof(tree));
        memset(arr,0,sizeof(arr));
        memset(input,0,sizeof(input));
        
        sum=0;
        
        cin >> n;
        
        for(int i=0; i<n; i++) cin >> input[i];
        for(int i=0; i<n; i++) {int x; cin >> x; arr[x] = i;}
	    
        for(int i=0; i<n; i++)    // 복잡도가  O(n * logn)
        {
            int that = arr[input[i]];
            sum += that - psum(that-1);
            add(that);
        }
        cout << sum << endl;
    }
}

august14 9년 전 1

cin -> scanf를 쓰니 시간안에 나오네요

cin/cout이 scanf/printf보다 느리기 때문에 입력이나 출력이 큰 경우 후자를 사용하는것을 권장합니다.

skeksk91 9년 전 0

답변 감사합니다. 어거스트님
이렇게 한 수 배웁니다 ^_^

h0ngjun7 9년 전 3

그리고 memset도 for문으로 초기화해주는 것보다 느려요. 참고하시길.

baekjoon 9년 전 1

참고로, 마지막 채점 데이터가 꼭 큰 데이터는 아닙니다.

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

문제

문제

출처

ICPC

9463 (순열그래프). 마지막 큰 데이터 채점중 시간초과가 되버려요

skeksk91 9년 전 0

august14 9년 전 1

skeksk91 9년 전 0

h0ngjun7 9년 전 3

baekjoon 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말