글 읽기 - 10999번 구간합 구하기 2 질문입니다.

mhkim4886 2년 전 1

Segtree with Lazy Propagation을 짰는데, 뭔가 문제가 있는지 틀렸습니다를 받았습니다.

특별하게 틀린 부분을 못 찾겠는데 제가 잘못 구현한 부분이 있을까요..?

감사합니다.

#include <cstdio>
typedef long long lli;

int n, m, k;
lli arr[1100000];
lli tree[4400000];
lli lazy[4400000];

lli init(int node, int start, int end)
{
    if(start == end) return tree[node] = arr[start];
    else return tree[node] = init(node*2, start, (start+end)/2) + init(node*2+1, (start+end)/2+1, end);
}

void update(int node, int start, int end, int upleft, int upright, lli diff)
{
    if(upright < start || end < upleft) return;
    tree[node] += lazy[node] * (end - start + 1);
    lazy[node*2] = lazy[node];
    lazy[node*2+1] = lazy[node];
    lazy[node] = 0;
    if(upleft <= start && end <= upright)
    {
        tree[node] += diff * (end - start + 1);
        lazy[node*2] += diff;
        lazy[node*2+1] += diff;
    }
    else
    {
        update(node*2, start, (start+end)/2, upleft, upright, diff);
        update(node*2+1, (start+end)/2+1, end, upleft, upright, diff);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
}

lli sum(int node, int start, int end, int left, int right)
{
    if(right < start || end < left) return 0;

    tree[node] += lazy[node] * (end - start + 1);
    lazy[node*2] += lazy[node];
    lazy[node*2+1] += lazy[node];
    lazy[node] = 0;
    if(left <= start && end <= right) return tree[node];
    return sum(node*2, start, (start+end)/2, left, right) + sum(node*2+1, (start+end)/2+1, end, left, right);
}

int main()
{
    scanf("%d %d %d", &n, &m, &k);

    for(int i = 1; i <= n; i++) scanf("%lld", &arr[i]);
    init(1, 1, n);

    for(int i = 1; i <= m+k; i++)
    {
        int a, b, c;
        lli d;
        scanf("%d %d %d", &a, &b, &c);
        if(a == 1)
        {
            scanf("%lld", &d);
            update(1, 1, n, b, c, d);
        }
        if(a == 2) printf("%lld\n", sum(1, 1, n, b, c));
    }
}

djm03178 2년 전 3

반례 드립니다.

2 2 1
3
3
1 1 2 -2
1 1 2 2
2 2 2
output: 5
correct answer: 3

3 3 2
-2
0
-1
1 1 3 -1
1 2 2 0
1 3 3 -2
2 1 1
2 3 3
output: -2 -3
correct answer: -3 -4

4 2 3
3
-1
-2
0
1 2 4 2
2 1 3
1 4 4 2
2 1 1
2 1 4
output: 4 3 6
correct answer: 4 3 8

mhkim4886 2년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

10999번 구간합 구하기 2 질문입니다.

mhkim4886 2년 전 1

djm03178 2년 전 3

mhkim4886 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말