글 읽기 - 런타임 에러의 이유를 못찾겠습니다

oheat87 1년 전 1

횐님들 안녕하십니까

제가 질문을 올리는 것은 다름이 아니오라 런타임 에러의 이유를 찾을수 없기 때문입니다.

50% 쯤에서 런타임 에러가 발생하는데 코드를 아무리 봐도 런타임 에러가 날만한 곳을 찾지 못하겠습니다.

알고리즘 동작 방식은 세그먼트 트리 하나를 놓고 주어진 직사각형 영역을 x값의 오름차순으로 스위핑 하면서 현재 직사각형이 몇개나 겹쳐있는지를 업데이트하는 방식으로 동작합니다. 직사각형의 x값을 기준으로 스위핑 하다가 x값이 달라지거나 또는 직사각형 시작부분인지 끝나는부분인지 여부가 달라지면 그때 주어진 집들(좌표들)이 지금 x값 구간에서 몇개나 직사각형에 겹치는지 세는 방식입니다.

미리 감사드립니다.

#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
#define MAXVAL 100000
#define MAXN 10000
#define MAXM 50000

typedef struct p_ {
    int x,y;
    p_():x(0),y(0){}
    p_(int xx, int yy):x(xx),y(yy){}
    p_& operator =(const p_& rside){
        x=rside.x; y=rside.y;
        return *this;
    }
} point;

struct comp_coord_x{
    bool operator() (const point& l, const point& r){
        return l.x<=r.x;
    }
};

typedef struct ls_{
    int x,y1,y2;
    bool end;
    ls_():x(0),y1(0),y2(0),end(true){}
    ls_(int xx, int y11, int y22, int ee):x(xx),y1(y11),y2(y22),end(ee){}
    ls_& operator =(const ls_& r){
        x=r.x; y1=r.y1; y2=r.y2; end=r.end;
        return *this;
    }
} ls;

struct comp_ls_x{
    bool operator ()(const ls& l, const ls& r){
        return l.x<r.x || (l.x==r.x && !l.end);
    }
};

typedef struct s_{
    int arr[(MAXVAL+1)*4+1];
    void init(){
        memset(arr,0,sizeof(arr));
    }
    int query(int y, int node, int nodeLeft, int nodeRight){
        if(y<nodeLeft || y>nodeRight) return 0;
        if(nodeLeft==nodeRight) return arr[node];
        int mid=(nodeLeft+nodeRight)/2;
        return arr[node]+query(y,node*2,nodeLeft,mid)+query(y,node*2+1,mid+1,nodeRight);
    }
    int query(int y){
        return query(y,1,0,MAXVAL);
    }
    void update(int left, int right, int val, int node, int nodeLeft, int nodeRight){
        if(nodeRight<left || right<nodeLeft) return;
        if(left<=nodeLeft && nodeRight<=right){
            arr[node]+=val;
            return;
        }
        int mid=(nodeLeft+nodeRight)/2;
        update(left,right,val,node*2,nodeLeft,mid);
        update(left,right,val,node*2+1,mid+1,nodeRight);
    }
    void update(int left, int right, int val){
        update(left,right,val,1,0,MAXVAL);
    }
} segtree;
segtree st;
point parr[MAXN];
ls larr[MAXM*2];

void solve(){
    int n,m; scanf("%d %d",&n,&m);
    for(int i=0; i<n; i++) scanf("%d %d",&parr[i].x,&parr[i].y);
    sort(parr,parr+n,comp_coord_x());
    for(int i=0; i<m; i++){
        scanf("%d %d %d %d",&larr[i*2].x,&larr[i*2+1].x,&larr[i*2].y1,&larr[i*2].y2);
        larr[i*2+1].y1=larr[i*2].y1;
        larr[i*2+1].y2=larr[i*2].y2;
        larr[i*2].end=false;
        larr[i*2+1].end=true;
    }
    sort(larr,larr+2*m,comp_ls_x());
    int ans=0,i=0,j=0,parr_len=n,larr_len=2*m;
    st.init();
    while(i<parr_len && j<larr_len){
        int cur_x=larr[j].x, next_x;
        bool cur_end=larr[j].end, next_end;
        while(j<larr_len && larr[j].x==cur_x && larr[j].end==cur_end){
            st.update(larr[j].y1,larr[j].y2,cur_end?-1:1);
            j++;
        }
        if(j>=larr_len) break;
        next_x=larr[j].x;
        next_end=larr[j].end;
        int from_x=cur_end?cur_x+1:cur_x;
        int to_x=next_end?next_x:next_x-1;
        while(i<parr_len && parr[i].x<=to_x){
            if(parr[i].x>=from_x) ans+=st.query(parr[i].y);
            i++;
        }
    }
    printf("%d\n",ans);
}

int main(){
    int t; scanf("%d",&t);
    while(t--) solve();
}

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

문제

문제

출처

ICPC

런타임 에러의 이유를 못찾겠습니다

oheat87 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말