글 읽기 - 동적 세그 mle 뭐가 문제일까요?

ploffer11 4년 전 0

조세퍼스 2, 구간합 구하기 등에서 그대로 복붙해 사용해본 결과 동적 세그 자체에 문제는 없어보이는데 (kth, update_idx, query 정상 작동 확인)

이 문제에만 제출하면 바로 mle를 받아요.. 뭐가 문제일까요 ㅠㅠ

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 987654321;
const int MOD = 1e9 + 7;

class DynamicSegmentTree
{
private:
    struct Node
    {
        int l, r;
        ll value, lazy;
        Node() : l(0), r(0), value(0), lazy(0) {}
    };
    vector<Node> tree;

    void _update_idx(int i, ll s, ll e, ll idx, ll diff)
    {
        if (s == e)
        {
            tree[i].value += diff;
            return;
        }

        ll m = (s + e) / 2;
        if (idx <= m)
        {
            if (tree[i].l == 0)
            {
                tree[i].l = tree.size();
                tree.push_back(Node());
            }
            _update_idx(tree[i].l, s, m, idx, diff);
        }
        else
        {
            if (tree[i].r == 0)
            {
                tree[i].r = tree.size();
                tree.push_back(Node());
            }
            _update_idx(tree[i].r, m + 1, e, idx, diff);
        }
        tree[i].value = tree[tree[i].l].value + tree[tree[i].r].value;
    }

    ll _query(int i, ll s, ll e, ll l, ll r)
    {
        if (i == 0 || e < l || s > r)
            return 0;
        else if (l <= s && e <= r)
            return tree[i].value;
        else
        {
            ll m = (s + e) / 2;
            return _query(tree[i].l, s, m, l, r) + _query(tree[i].r, m + 1, e, l, r);
        }
    }

    ll _kth(int i, ll s, ll e, ll sum)
    {
        if (s == e)
            return s;
        ll m = (s + e) / 2;
        if (tree[tree[i].l].value < sum)
            return _kth(tree[i].r, m + 1, e, sum - tree[tree[i].l].value);
        else
            return _kth(tree[i].l, s, m, sum);
    }

public:
    ll s, e;
    DynamicSegmentTree()
    {
        tree.push_back(Node());
        tree.push_back(Node());
        this->s = 0;
        this->e = (ll)1e18 + 5;
    }

    ll query(ll l, ll r)
    {
        return _query(1, s, e, l, r);
    }

    void update_idx(ll idx, ll diff)
    {
        _update_idx(1, s, e, idx, diff);
    }

    ll kth(ll sum)
    {
        return _kth(1, s, e, sum);
    }
};

ll snow[100005];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    DynamicSegmentTree Tree;

    ll n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> snow[i];
        Tree.update_idx(snow[i], 1);
    }

    while (m--)
    {
        int q;
        cin >> q;
        if (q == 1)
        {
            int i, x;
            cin >> i >> x;
            Tree.update_idx(snow[i], -1);
            Tree.update_idx(snow[i] + x, 1);
            snow[i] += x;
        }
        else if (q == 2)
        {
            int i, x;
            cin >> i >> x;
            Tree.update_idx(snow[i], -1);
            Tree.update_idx(snow[i] - x, 1);
            snow[i] -= x;
        }
        else if (q == 3)
        {
            ll l, r;
            cin >> l >> r;
            cout << Tree.query(l, r) << '\n';
        }
        else
        {
            int t;
            cin >> t;
            cout << Tree.kth(n - t + 1) << '\n';
        }
    }
}

YunGoon 4년 전 1

당신의 메모리, lazy로 대체되었다.

ploffer11 4년 전 1

is this problem?

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

문제

문제

출처

ICPC

동적 세그 mle 뭐가 문제일까요?

ploffer11 4년 전 0

YunGoon 4년 전 1

ploffer11 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말