글 읽기 - 8퍼에서 시간초과가납니다 어디서 잘못된걸까요 ㅜ?

isvara 4년 전 0

swap도 했고 입출력도 빠를텐데 8퍼에서 시간초과가 나옵니다. 어떤부분에서 잘못됬을까요 ㅜ?

#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;

int N, Q;
int a[100001];
vector<ll>treeNode;

ll init(int start, int end, int node) {
	if (start == end)
		return treeNode[node] = a[start];
	int mid=(start + end) / 2;
	
	ll left = init(start, mid, node*2);
	ll right = init(mid + 1, end, node * 2 + 1);

	return treeNode[node] = left + right;
}
ll query(int start, int end, int node, int NodeLeft, int NodeRight) {
	if (start > NodeRight || end < NodeLeft)
		return 0;
	if (NodeLeft <= start && end <= NodeRight)
		return treeNode[node];
	
	int mid = (start + end) / 2;
	
	ll left = query(start, mid, node * 2, NodeLeft, NodeRight);
	ll right = query(mid + 1, end, node * 2 + 1, NodeLeft, NodeRight);

	return left + right;
}
ll update(int start, int end, int node, int target, int value) {
	if (start == end)
		return treeNode[node] = value;

	if (target < start || end < target)
		return treeNode[node];

	int mid = (start + end) / 2;

	ll left = update(start, mid, node * 2, target, value);
	ll right = update(mid + 1, end, node * 2 + 1, target, value);

	return treeNode[node] = left+right;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> Q;

	for (int i = 1; i <= N; i++)
		cin >> a[i];
	//seg initial
	int h = ceil(log2(N));
	treeNode=vector<ll>((1 << (h + 1)),0);
	init(1, N, 1);

	for (int i = 1; i <= Q; i++)
	{
		int x, y, target, value;
		
		cin >> x >> y >> target >> value;
		if (x > y)swap(x, y);

		cout<<query(1, N, 1, x, y)<<endl;
		
		a[target] = value;
		update(1, N, 1, target, value);
	}
}

djm03178 4년 전 1

endl을 쓰면 cin.tie(0)가 무의미해집니다. '\n'을 사용하세요.

isvara 4년 전 0

아.. 그렇군요 "\n" 별대수롭지 않게느꼇습니다. 답변해주셔서 감사합니다 .. 고쳐도 틀리긴한데 고쳐봐야겠습니다

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

문제

문제

출처

ICPC

8퍼에서 시간초과가납니다 어디서 잘못된걸까요 ㅜ?

isvara 4년 전 0

djm03178 4년 전 1

isvara 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말