글 읽기 - 시간초과가 어디서 나는걸까요? (pq사용)

yoodori5 3년 전 2

우선순위 큐에 입력받음과 동시에 {-값,인덱스}의 페어로 넣은뒤

우선순위 큐에 저장된 최솟값을 뽑습니다.

이때 그 값의 인덱스가 i-l+1보다 작다면 pop해서 범위안에 들어오는 최솟값을 찾아줍니다.

이후 그 값을 출력합니다.

#include <stdio.h>
#include <queue>

using namespace std;

priority_queue<pair<int,int> > pq;

int l,n;

int main(){
	scanf("%d %d",&n,&l);
	for(int i=0;i<n;i++){
		int a;
		scanf("%d",&a);
		pq.push({-a,i});
		while(pq.top().second<i-l+1){
			pq.pop();
		}
		printf("%d ",-pq.top().first);
	}
	
}

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

문제

문제

출처

ICPC

시간초과가 어디서 나는걸까요? (pq사용)

yoodori5 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말