글 읽기 - 2%에서 틀리는데 어떤 반례가 있는지 모르겠어요

edwardblue 3년 전 0

데이터도 50개정도 만들어서 넣어봤는데 다 일치하는데

어떤 반례가 있는지 궁금해요

세그먼트 트리를 사용했습니다

#include <bits/stdc++.h>
#define fst first
#define snd second
#define pii pair<int, int>

typedef long long ll;
using namespace std;
vector<int> arr;
struct Seg{
    int n;
    vector<pii> t;
    void init(vector<int> &arr)
    {
        n = arr.size();
        t.resize(2*n);
        for (int i=0;i<n;i++) {
            t[n+i].snd=arr[i];
            t[n+i].fst=i+1;
        }
        for (int i=n-1;i>0;i--) {
            if (t[i*2].snd<=t[i*2+1].snd) {
                t[i]=t[i*2];
            }
            else {
                t[i]=t[i*2+1];
            }
        }
    }
    void update(int x, ll val)
    {
        t[x+=n].snd = val;
        while (x>>=1) {
            if (t[x*2].snd<=t[x*2+1].snd) {
                t[x]=t[x*2];
            }
            else {
                t[x]=t[x*2+1];
            }
        }
    }
    int query(int l, int r)
    {
        int m = INT_MAX;
        int idx = 1e9+7;
        l+=n;
        r+=n;
        while (l <= r) {
            if ((l&1)&&m>=t[l].snd) {
                m=t[l].snd;
                idx = t[l].fst;
            }
            if (!(r&1)&&t[r].snd<m) {
                m=t[r].snd;
                idx = t[r].fst;
            }
            l++;
            r--;
            l >>= 1;
            r >>= 1;
        }
        return idx;
    }
}seg;
int main()
{
    // freopen("14428.in", "r", stdin);
    // freopen("14428_my.out", "w", stdout);
    int n, m;
    scanf("%d",&n);
    for (int i=0;i<n;i++) {
        int t;
        scanf("%d",&t);
        arr.push_back(t);
    }
    scanf("%d",&m);
    seg.init(arr);
    for (int i=0;i<m;i++) {
        int a, b, c;
        scanf("%d %d %d",&a,&b,&c);
        if (a==1) seg.update(b-1, c);
        else printf("%d\n",seg.query(b-1,c-1));
    }
}

harinboy 3년 전 2

아래와 같은 경우 틀린 답이 나오게 됩니다.

1 1 1 1 1

2 1 3

정답: 1

출력: 2

edwardblue 3년 전 0

트리의 왼쪽에 있다고 무조건 더 인덱스가 작은게 아니네요;; 감사합니다.

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

문제

문제

출처

ICPC

2%에서 틀리는데 어떤 반례가 있는지 모르겠어요

edwardblue 3년 전 0

harinboy 3년 전 2

edwardblue 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말