글 읽기 - 17353 c++ 질문입니다.

yohanroh 2년 전 1

나름 대로 테스트케이스도 만들어서 돌려보았는데 코드에서 어디가 틀렸는지 잘 모르겠습니다.

[L, R] 쿼리에 대해서 L, R 구간에 1 ~ (R - L + 1)을 더하는 과정에서

M = (L + R) / 2라고 두고 L ~ M 구간에는 1 ~ M - L + 1을 더해주고 M + 1 ~ R 구간에는 M - L + 2 ~ R - L + 1을 더해주는 것으로 처리했습니다.

#include <iostream>

using namespace std;

typedef long long int ll;

int n, q;
ll seg[1 << 21];

struct info
{
    ll s, e;
};

info lazy[1 << 21];

ll sum(ll s, ll e)
{
    return (e - s + 1) * (s + e) / 2;
}

void propagate(int loc, int s, int e)
{
    if (lazy[loc].s || lazy[loc].e) {
        seg[loc] += sum(lazy[loc].s, lazy[loc].e);
        if (s < e) {
            ll m = (lazy[loc].s + lazy[loc].e) / 2;
            lazy[2 * loc].s += lazy[loc].s;
            lazy[2 * loc].e += m;
            lazy[2 * loc + 1].s += m + 1;
            lazy[2 * loc + 1].e += lazy[loc].e;
        }
    }
    lazy[loc].s = lazy[loc].e = 0;
}

void update(int loc, int s, int e, int l, int r, ll u, ll v)
{
    propagate(loc, s, e);
    if (r < s || e < l) return;
    if (l <= s && e <= r) {
        ll U = u + s - l, V = v - r + e;
        seg[loc] += sum(U, V);
        if (s < e) {
            ll M = (U + V) / 2;
            lazy[2 * loc].s += U;
            lazy[2 * loc].e += M;
            lazy[2 * loc + 1].s += M + 1;
            lazy[2 * loc + 1].e += V;
        }
    }
    else {
        int m = (s + e) / 2;
        update(2 * loc, s, m, l, r, u, v);
        update(2 * loc + 1, m + 1, e, l, r, u, v);
        seg[loc] = seg[2 * loc] + seg[2 * loc + 1];
    }
}

ll query(int loc, int s, int e, int l, int r)
{
    propagate(loc, s, e);
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) return seg[loc];
    else {
        int m = (s + e) / 2;
        return query(2 * loc, s, m, l, r) + query(2 * loc + 1, m + 1, e, l, r);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        ll a;
        cin >> a;
        update(1, 1, n, i, i, a, a);
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        if (x > 1) {
            int a;
            cin >> a;
            cout << query(1, 1, n, a, a) << "\n";
        }
        else {
            int a, b;
            cin >> a >> b;
            update(1, 1, n, a, b, 1, (ll)(b - a + 1));
        }
        /*
        cout << i + 1 << " : ";
        for (int i = 1; i <= n; i++) {
            cout << query(1, 1, n, i, i) << " ";
        }
        cout << "\n";
        */
    }
    return 0;
}

wnsduds1 2년 전 2

10
1 2 3 4 5 6 7 8 9 10
6
1 1 5
1 2 6
1 5 10
1 5 10
1 1 8
2 9

ans 19

wrong answer :30

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

문제

문제

출처

ICPC

17353 c++ 질문입니다.

yohanroh 2년 전 1

wnsduds1 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말