글 읽기 - 왜 틀릴까요..

sksdong1 7년 전 0

펜윅트리로 풀었는데요.

현재 나무 위치 x를 기준으로 왼쪽으로는 (x보다 작은 나무의 수*x) - (x보다 작은 나무의 전체 길이)

오른쪽은 (x보다 큰 나무의 전체길이) - (x보다 큰 나무의 수 *x)

머가 문제일까요

#include<stdio.h>
#include<vector>
using namespace std;
#define MAX_N 200002
#define MOD 1000000007LL
typedef long long ll;
ll sum(int pos,vector<ll>& array){
	ll ret=0;
	while(pos>0) ret+=array[pos],pos-=(pos&-pos);
	return ret;
}
void add(int pos,ll val,vector<ll>& array){
	while(pos<MAX_N) array[pos]+=val,pos+=(pos&-pos);
}

int main(){
	int n;
	vector<ll> c(MAX_N,0);
	vector<ll> s(MAX_N,0);
	scanf("%d",&n);
	ll ret=1;
	for(int i=0;i<n;++i){
		int u;
		scanf("%d",&u);
		u++;
		if(ret==0) ret=1;
		ret=((((sum(u-1,c)*u)%MOD-sum(u-1,s)+MOD)%MOD)*ret)%MOD;
		ret+=(( (MOD+(sum(MAX_N-1,s)-sum(u,s)+MOD)%MOD- ( ((MOD+sum(MAX_N-1,c)-sum(u,c) )%MOD)*u))%MOD)*ret) %MOD;
		add(u,1,c);
		add(u,u,s);
		
	}
	printf("%lld",ret);
}

yohan5050 7년 전 1

27, 28번째 줄에서 ret값에 각 나무에 대한 비용을 곱해서 저장하는 부분에서 문제가 있는 것 같아요

입력
5
2 3 0 1 4
출력
200

이 예제도 위의 코드로 돌려보면 틀리게 나와요.
그리고 27, 28번째 줄에서 어떤 문제가 있는지는 잘 모르겠지만
그냥 ret외에 다른 변수를 하나 선언어서 각 나무에 대한 비용을 저장해놓고,
ret은 각 나무에 대한 비용의 곱을 저장하는 용도로만 쓰시면 간단해져서 문제 생길 일이 거의 없을거에요.
27, 28줄만 수정하시면 맞으실 것 같아요

sksdong1 7년 전 1

고마워용 ㅋㅋ 저 부분만 수십번 고쳤는데.. 다시 해봐야겠어요

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

문제

문제

출처

ICPC

왜 틀릴까요..

sksdong1 7년 전 0

yohan5050 7년 전 1

sksdong1 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말