글 읽기 - 2357 어떤 이유로 시간초과가 나는지 궁금합니다...

lsvk9921 1년 전 0

코드는 다음과 같습니다..

함수 반환형이 pair<int,int> 인것 때매 그런거 같기도하고...

잘 모르겠습니다 어느 부분에서 속도가 느려지는 것일 까요? ㅠㅠ

#include<iostream>
#include<algorithm>
#include<vector>


using namespace std;

int N;int M;
int arr[100001];
// min, max
pair<int,int> segtree[100001*4];
pair<int,int> init(int start,int end,int node){

    if(start==end){
        segtree[node].first=arr[start];
        segtree[node].second=arr[start];
        return segtree[node];
    }

    int mid=(start+end)/2;
    pair<int,int> left=init(start,mid,node*2);
    pair<int,int> right=init(mid+1,end,node*2+1);
    segtree[node]={min(left.first,right.first),max(left.second,right.second)};
    return segtree[node];
    // return segtree[node]={min(init(start,mid,node*2).first,init(mid+1,end,node*2+1).first),
    // max(init(start,mid,node*2).second,init(mid+1,end,node*2+1).second)};
}

pair<int,int> find(int start,int end,int node,int left,int right){
    if(start>right||end<left){
        return {1000000001,0};
    }
    if(left<=start&&end<=right){
        return segtree[node];
    }
    int mid=(start+end)/2;
    pair<int,int> rtn;
    pair<int,int> l;pair<int,int>r;
    l=find(start,mid,node*2,left,right);
    r=find(mid+1,end,node*2+1,left,right);
    rtn={min(l.first,r.first),max(l.second,r.second)};
    return rtn;
}
int main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    cin>>N>>M;
    for(int i=0;i<N;i++){
        scanf("%d",&arr[i]);
    }   
    init(0,N-1,1);
    int a,b;
    vector<pair<int,int>> ans;
    for(int i=0;i<M;i++){
        cin>>a>>b;
        // left 와 right 는 arr의 인덱스이다.
        ans.push_back(find(0,N-1,1,a-1,b-1));
    }
    for(int i=0;i<ans.size();i++){
        cout<<ans[i].first<<" "<<ans[i].second<<endl;
    }
}

layner 1달 전 0

endl 을 '\n'으로 바꾸니까 통과하더라구요..

빡빡하네요 시간제한 후

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

문제

문제

출처

ICPC

2357 어떤 이유로 시간초과가 나는지 궁금합니다...

lsvk9921 1년 전 0

layner 1달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말