글 읽기 - 틀렸습니다가 뜨는데 반례를 찾지 못하겠습니다. 세그먼트트리 쓰지 않았습니다.

yony1995 5년 전 0

세그먼트 트리는 쓰지 않았습니다.

2개의 배열에 합과 항목을 따로 저장한 뒤 항목만 갱신하고

업데이트 내용을 vector에 저장하는 방식을 이용했습니다.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <utility>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>

using namespace std;

#define MAX 1000001

int n, m, k;

long long arr[MAX]; //항목을 저장
long long arr2[MAX]; //합을 저장, 원본 그대로 갱신하지 않음

vector<pair<long long, long long>> vec; 
// 갱신되는 내용을 저장

int main(void)
{
	int i, j;

	long long a, b, c;
	long long total;

	cin >> n >> m >> k;

	for (i = 1; i <= n; i++)
	{
		cin >> arr2[i];  
		//arr2에 idx에 해당하는 수 저장
		arr[i] = arr[i - 1] + arr2[i];  
		//arr에 idx까지의 합을 저장
	}

	for (i = 0; i < m + k; i++)
	{
		cin >> a >> b >> c;

		if (a == 1)  //1번 연산
		{
			vec.push_back(make_pair(b, c - arr2[b]));
			//vector에 바꿀 idx와 원래 수와의 차이를 저장
			//업데이트가 일어날때마다 업데이트 사항을 저장
			arr2[b] = c;
			//arr2만 갱신 arr은 갱신하지 않음
		}

		else
		{
			total = arr[c] - arr[b - 1];
			//원래 b ~ c 까지의 합을 저장 

			for (j = 0; j < vec.size(); j++)
			{
				if (c < vec[j].first) continue;
				//c가 갱신되는 idx보다 크거나 같아야 영향을 받음
				else
				{
					total += vec[j].second;
					//원래 값에 갱신되는 차이를 반영
				}
			}

			printf("%lld\n", total);
		}
	}
}

edenooo 5년 전 1

59번째 라인 c가 idx보다 크거나 같은지는 확인했지만, b가 idx보다 작거나 같은지는 확인하지 않았네요.

edenooo 5년 전 1

그리고 저렇게 짜면 최악의 경우 O(MN)으로 시간 초과가 나오지 않을까요?

yony1995 5년 전 1

if (c < vec[j].first || b > vec[j].first) continue;

이런식으로 수정하여 정답입니다 띄웠습니다. b가 큰경우를 간과했네요.

감사합니다. 다행히 시간초과가 뜨진 않아요.

djm03178 5년 전 2

O(MN)이라는 이야기를 듣고 데이터를 추가해야 하나 달려와봤는데, 안타깝게도 O(N+MK)인 것 같네요.

edenooo 5년 전 1

@djm03178 네 제가 잘못 봤어요 ㅠㅜ

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

문제

문제

출처

ICPC

틀렸습니다가 뜨는데 반례를 찾지 못하겠습니다. 세그먼트트리 쓰지 않았습니다.

yony1995 5년 전 0

edenooo 5년 전 1

edenooo 5년 전 1

yony1995 5년 전 1

djm03178 5년 전 2

edenooo 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말