글 읽기 - ㅠㅠ 제발.. 틀린부분좀 찾아주세요 ㅜ 뭐가 틀린것일까요.,?(주석포함)

dorinee_restart 2년 전 0

주석 달았습니다!

그리고,, 0일때 예외처리를 bool 배열로 받아서 처리를 했는데

계속 4퍼틀이 나오네요.. 나름 0 들어가는 예외를 찾았을때는 맞았는데 왜그런걸까요?

#include<iostream>
#include<vector>
#define ll long long 
#define endl "\n"
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
ll n, m, k;
ll arr[1000001];
ll tree[4000004]; 
bool checki[1000001];

ll init(ll node, ll start, ll end) { // init함수 
	if (start == end)return tree[node] = arr[start]; // 리프일때는 해당지점 원소값 반환
	else { // 아닐때는 재귀적으로 구간 나눠줌
		ll mid = (start + end) / 2;
        ll aa = init(node * 2, start, mid)% 1000000007;
        ll bb = init(node * 2 + 1, mid + 1, end)% 1000000007;
		return tree[node] = (aa*bb)% 1000000007;
	}
}
void update(ll node, ll start, ll end, ll idx, ll change) {
	ll mid = (start + end) / 2;

	if (start == end) {// 리프노드일때
		tree[node] /= arr[start];// 현재 노드값에서 리프값 나눠줌
		tree[node] *= change;// 노드값에다가 change를 곱하면 update완료
		return;
	}
	if (idx > mid) {
		tree[node] /= arr[idx]; // arr[idx]값을 현재 노드값과 나눔
        tree[node] = tree[node]% 1000000007; // 나머지 연산해주고
		tree[node] *= change;// 노드값에 change를 곱하면 update끝
        tree[node] = tree[node]% 1000000007;
        // 그 이후에 재귀적으로 같은방식
		update(node * 2 + 1, mid + 1, end, idx, change);
	}
	if (idx <= mid) {// 이것도 마찬가지
		tree[node] /= arr[idx];
        tree[node] = tree[node]% 1000000007;
		tree[node] *= change;
        tree[node] = tree[node]% 1000000007;
		update(node * 2, start, mid, idx, change);
	}
}
ll mul(ll node, ll start, ll end, ll left, ll right) {
	if (left > end or right < start) return 1;// 해당범위에 안들어오면 1 반환
	if (left <= start and end <= right)return tree[node];// 범위와 맞거나 리프일때는 노드값반환
	ll mid = (start + end) / 2; // 나머지애들은 재귀적으로 실행
	ll aaa = mul(node * 2, start, mid, left, right) % 1000000007;
	ll bbb = mul(node * 2 + 1, mid + 1, end, left, right) % 1000000007;
	return (aaa* bbb) % 1000000007;
}

int main() {
	fastio;
	cin >> n >> m >> k;
	for (ll i = 1; i <= n; i++) {
		cin >> arr[i];
		checki[i] = 0; // 0 체크용도 bool 배열
    }
	init(1, 1, n);
	for (ll i = 0; i < m + k; i++) {
		ll a, b, c;
		cin >> a;
		if (a == 1) {
			cin >> b >> c;
			if (c == 0) { // 0을 update 시키면
				checki[b] = 1; // 체크배열에 해당위치 1 로 바꾸고
				continue; // update함수엔 들어가지 않는다. update함수에 들어가게된다면 곱셈연산
                //때문에 문제가 된다.
			}
			else { // c가 0 이 아니면 상관없다.
				if (checki[b] == 1) checki[b] = 0; // 하지만 이전에 check배열에서 
                //b인덱스가 1 이였을수도 있기 때문에 한번 확인만 해주고
          		update(1, 1, n, b, c);//update를 실행해준다.
			}
		}
		if (a == 2) {
			cin >> b >> c;
			for (int i = b; i <= c; i++) { // b부터 c까지 check배열에서 1 이 있었다면
				if (checki[i] == 1) { check = true;  break; } // check 변수=1 하고 종료
			}
			if(check!=true )  cout << mul(1, 1, n, b, c) << endl;// 체크배열에1이 없었으면 그냥 mul출력

			if (check == true ) { cout << 0 << endl; check = false; }// check변수가 1이면 해당구간에
            // 0이 있다는 의미니깐 그냥 0 출력하고 check 변수는 다시 false로 해준다.
	    }
    }
	return 0;
}

0000000000 2년 전 0

이런 식으로 checki 배열을 유지하는 식으로 풀면 최악의 경우 시간복잡도가 O(N(M+K))가 되어 시간초과가 나올 수도 있습니다. 굳이 checki 배열을 유지하지 않고 c가 0이어도 update를 계속 해 주셔야 합니다.

dorinee_restart 2년 전 0

알겠습니다! 다시한번 시도해볼께요. 알려주셔서 감사합니다..!

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

문제

문제

출처

ICPC

ㅠㅠ 제발.. 틀린부분좀 찾아주세요 ㅜ 뭐가 틀린것일까요.,?(주석포함)

dorinee_restart 2년 전 0

0000000000 2년 전 0

dorinee_restart 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말