글 읽기 - 시간초과가 뜨는 이유를 모르겠습니다

typebreaker 7년 전 0

처음에는 원형 큐와 비슷한 방법으로 풀었는데 시간초과가 떠서

세그먼트 트리로 풀었는데도 시간초과가 떠서

세그먼트트리에서 구간 단위로 입력시키도록 했는데도 시간 초과가 뜹니다

혹시 제가 간과한게 있을까요?

#include <iostream>
#include <cstdio>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
long long int seg[400008];
long long int lazy[400008];
void update(int now, int start, int end, int index, long long int diff) {
	if (index < start || index > end) return;
	seg[now] = seg[now] + diff;
	if (start != end) {
		update(now * 2 + 1, start, (start + end) / 2, index, diff);
		update(now * 2 + 2, (start + end) / 2 + 1, end, index, diff);
	}
}
long long int sum(int now, int start, int end, int left, int right)
{
	if (left > end || right < start) {
		return 0;
	}
	if (left <= start && end <= right) {
		return seg[now];
	}
	return sum(now * 2 + 1, start, (start + end) / 2, left, right) + sum(now * 2 + 2, (start + end) / 2 + 1, end, left, right);
}
//diff=val-arr[index];
void updatelazy(int now, int start, int end)
{
	if (lazy[now] != 0)
	{
		seg[now] = seg[now] + (end - start + 1) * lazy[now];
		if (start != end)
		{
			lazy[now * 2 + 1] += lazy[now];
			lazy[now * 2 + 2] += lazy[now];
		}
		lazy[now] = 0;
	}
}
void update2(int now, int start, int end, int i, int j, long long int diff)
{
	updatelazy(now, start, end);
	if (i > end || j < start) return;
	if (i <= start && end <= j)
	{
		seg[now] += (end - start + 1)*diff;
		if (start != end)
		{
			lazy[now * 2 + 1] += diff;
			lazy[now * 2 + 2] += diff;
		}
		return;
	}
	update2(now * 2 + 1, start, (start + end) / 2, i, j, diff);
	update2(now * 2 + 2, (start + end) / 2 + 1, end, i, j, diff);
	seg[now] = seg[now * 2 + 1] + seg[now * 2 + 2];
}
long long int sum2(int now, int start, int end, int left, int right)
{
	updatelazy(now, start, end);
	if (left > end || right < start) {
		return 0;
	}
	if (left <= start && end <= right) {
		return seg[now];
	}
	return sum2(now * 2 + 1, start, (start + end) / 2, left, right) + sum2(now * 2 + 2, (start + end) / 2 + 1, end, left, right);
}
int main()
{
	int testcase = 0;
	long long int ci = 0;
	long long int ki = 0;
	long long int s = 0;
	long long int a, b = 0;
	int i, j = 0;
	int N = 0;
	int D = 0;
	long long int res = 0;
	long long int start = 0;
	cin >> testcase;
	while (testcase--)
	{
		res = 0;
		start = 0;
		for (int i = 0; i < 2 * N; i++)
		{
			seg[i] = 0;
			lazy[i] = 0;
		}
		cin >> N >> D >> s >> a >> b;
		for (int i = 1; i <= D; i++) {
			ci = s % N + 1;
			s = (s * a + b) % 1000000007;
			ki = s % N + 1;
			s = (s * a + b) % 1000000007;
			if (ci + start >= N)
			{
				update2(0, 0, N - 1, start, N - 1, i);
				update2(0, 0, N - 1, 0, (start + ci) % N - 1, i);
			}
			else
				update2(0, 0, N - 1, start , ci + start - 1, i);
			
			/*for (j = 0; j < ci; j++)
			{
				update(0, 0, N - 1, (j + start) % N, i);
			}*/
			start = (start + ci) % N;
			res = res + sum2(0, 0, N - 1, (ki + start -1) % N , (ki + start -1) % N );

		}
		cout << res << endl;
	}
	return 0;
}

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

문제

문제

출처

ICPC

시간초과가 뜨는 이유를 모르겠습니다

typebreaker 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말