글 읽기 - 시간초과 질문드립니다.

ung27540421 5년 전 0

입력받고 첫번째부터 i번째까지 합을 저장하는 부분에서 O(N)

각 질의에 출력하는 부분은 lower_bound를 써서 총 O(MlogN)으로 짰는데 시간초과가 납니다.

N, M 200000으로 랜덤 테스트 케이스 만들어서 돌려봐도 200ms쯤에 끝나는데 왜 시간초과가 날까요? ㅜㅜ

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	vector<int> sum(N + 1);
	sum[0] = 0;
	for(int i = 1; i <= N; i++) {
		int T;
		cin >> T;
		sum[i] = sum[i - 1] + T;
	}
	while(M--) {
		int T;
		cin >> T;
		vector<int>::iterator i = lower_bound(sum.begin(), sum.end(), T);
		if(i == sum.end() || T < *i)
			i--;
		cout << i - sum.begin() << endl;
	}

	return 0;
}