글 읽기 - c++ stl map으로 구현하면 시간초과가 납니다...

loveleesj 3년 전 0

map나 unordered_map의 각 node에 접근하는데 최대 log(N^2)만큼 걸려서

sort후 upper_bound, lower_bound로 답을 구하는 것과 똑같은 O(N^2 * log(N^2)) 일것 같은데 이렇게 재출하면 시간초과가 납니다...

같은 시간복잡도여도 이렇게 유의미한 차이가 나나요?

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n, s[4000][4];
	unsigned long long ans = 0;
	unordered_map<int,int> m1, m2;
	
	cin >> n;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < 4; j++)
			cin >> s[i][j];
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			m1[s[i][0]+s[j][1]]++;
			m2[s[i][2]+s[j][3]]++;
		}
	}
	
	for(auto x: m1)
		ans += x.second*m2[-x.first];
	
	cout << ans;
	
	return 0;
}

Green55 3년 전 2

set, map은 유의미할 정도로 log가 느린 경우가 많습니다.

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

문제

문제

출처

ICPC

c++ stl map으로 구현하면 시간초과가 납니다...

loveleesj 3년 전 0

Green55 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말