글 읽기 - treap 을 이용했는데 69% 에서 시간초과가 납니다...

comseung18 3년 전 0

종만북의 treap 을 이용하여 그대로 구현하였는데, 시간초과가 납니다.

제가 알기로는treap 의시간 복잡도가 insert, countLessThen 이 모두 logn 으로 알고있는데요 ㅠ.ㅠ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;

#define endl '\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);

typedef int KeyType;
// 트립의 한 노드를 저장한다.
struct Node{
	// 노드에 저장된 원소
	KeyType key;
	// 이 노드의 우선순위(priority)
	// 이 노드를 루트로 하는 서브트리의 크기(size)
	int priority, size;
	// 두 자식 노드의 포인터
	Node *left, *right;
	// 생성자에서 난수 우선순위를 생성하고, size와 left/right를 초기화한다.
	Node(const KeyType& _key) :key(_key), priority(rand()),
	size(1), left(NULL), right(NULL){}
	
	void setLeft(Node* newLeft) { left = newLeft; calcSize(); }
	void setRight(Node* newRight) { right = newRight; calcSize(); }
	// size 멤버를 갱신한다.
	void calcSize(){
		size = 1;
		if(left) size += left->size;
		if(right) size += right->size;
	}
};

typedef pair<Node*, Node*> NodePair;
// root를 루트로 하는 트립을 key 미만의 값과 이상의 값을 갖는
// 두 개의 트립으로 분리한다.
NodePair split(Node* root, KeyType key){
	if(root == NULL) return NodePair(NULL, NULL);
	// 루트가 key 미만이면 오른쪽 서브트리를 쪼갠다.
	if(root->key < key){
		NodePair rs = split(root->right, key);
		root->setRight(rs.first);
		return NodePair(root, rs.second);
	}
	NodePair ls = split(root->left, key);
	root->setLeft(ls.second);
	return NodePair(ls.first, root);
}

// root 를 루트로 하는 트립에 새 노드 node를 삽입한 뒤 결과 트립의
// 루트를 반환한다.
Node* insert(Node* root, Node* node){
	if(root == NULL) return node;
	// node가 루트를 대체해야 한다. 해당 서브트리를 반으로 잘라
	// 각각 자손으로 한다.
	if( root->priority < node->priority){
		NodePair splitted = split(root, node->key);
		node->setLeft(splitted.first);
		node->setRight(splitted.second);
		return node;
	}
	else if(node -> key < root->key)
		root->setLeft(insert(root->left, node));
	else
		root->setRight(insert(root->right,node));
	return root;
}

// key 보다 작은 키값의 수를 반환한다.
int countLessThen(Node* root, KeyType key){
	if(root == NULL) return 0;
	if(root -> key >= key)
		return countLessThen(root->left, key);
	int ls = (root->left ? root->left->size : 0);
	return ls + 1 + countLessThen(root->right, key);
}

int main(){
    fastio;
    int N;
    cin >> N;
    Node* root = nullptr;

    ll cnt = 0;
    rep(i,N){
      int t;
      cin >> t;
      cnt += i - countLessThen(root, t);
      root = insert(root, new Node(t));
    }
    cout << cnt;
    return 0;
}

comseung18 3년 전 0

결국 세그먼트로 풀었습니다,,

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

문제

문제

출처

ICPC

treap 을 이용했는데 69% 에서 시간초과가 납니다...

comseung18 3년 전 0

comseung18 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말