글 읽기 - 왜 틀렸는지를 모르겠습니다... (돌아버리겠네...)

tmdghks9574 3년 전 0

세그먼트트리를 사용해서 구간합을 구하고

1부터 처음엔 끝까지, 그다음 반땅, 그다음 작으면 반땅 크면 반땅위 이렇게 계속 가서 최종적으로

pos가 딱 맞게 떨어지거나, 그전 부대 구간보단 크고 그다음 부대 구간보단 작으면 그 중간값을 출력해줬는데

왜 틀렸을까유? (주석처리 한 부분은 있어도 틀리고 없어도 틀립니당)

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
ll arr[1000001];
ll seg[3000001];
long long init(int left, int right, int node)
{
    if(left == right)
    {
        seg[node] = arr[left];
        return seg[node];
    }

    int mid = (left+right)/2;
    return seg[node] = init(left,mid,node*2) + init(mid+1,right,node*2+1);

}

void update(int node, int left, int right, int pos, int diff)
{
    if(pos < left || pos > right)
        return ;
    seg[node] += diff;
    if(left == right)
        return ;
    int mid = (left+right)/2;
    update(node*2,left,mid,pos,diff);
    update(node*2+1,mid+1,right,pos,diff);
}

long long find_sum(int node, int left, int right, int from, int to)
{
    if(right < from || left > to)
        return 0;

    if(left >= from && right <= to)
        return seg[node];

    int mid = (left+right)/2;
    return find_sum(node*2 , left, mid, from, to) + find_sum(node*2+1, mid+1, right, from, to);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    init(1,n,1);
    int m; cin >> m;
    for(int i = 0; i < m; i++)
    {
        int a; cin >> a;
        if(a == 1)
        {
            int b,c; cin >> b >> c;
            int diff = c;
            arr[b] += diff;
            update(1,1,n,b,diff);
        }
        else
        {
            int left = 1, right = n;
            int sol; cin >> sol;
            int pos = 30;
            int k = 2;
            while(pos--)
            {
                ll ans = find_sum(1,1,n,left,right);
                ll ans2 = find_sum(1,1,n,left,right-1);
                if(sol == ans || (ans2 < sol && ans > sol))
                    break;
                else if(sol > ans)
                {
                    right = right + n/k;
                    k *= 2;
                }
                else
                {
                    right = right - n/k;
                    k *= 2;
                }
            }
            cout << right << endl;
        }
    }
}

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

문제

문제

출처

ICPC

왜 틀렸는지를 모르겠습니다... (돌아버리겠네...)

tmdghks9574 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말