글 읽기 - 14413 Mo's 질문입니다.

0000000000 2년 전 0

수의 범위가 너무 커서 압축을 해 준 다음 Mo's를 썼습니다. 검색해서 나온 다른 분들 코드와도 별로 다른 것 같지 않은데 왜 틀리는지 이유 또는 반례를 알 수 있을까요?

#include<bits/stdc++.h>
using namespace std;
int sn;
struct Q{
    int idx,st,ed;
    bool operator<(const Q& a)const{
        if(st/sn!=a.st/sn) return st/sn<a.st/sn;
        return ed<a.ed;
    }
};
vector<int> a(500005);
vector<int> t(500005);
vector<Q> q;
vector<int> res(500005);
vector<int> c(500005);
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n,m; cin>>n>>m; sn=sqrt(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        t[i]=a[i];
    }
    //압축
    sort(t.begin(),t.begin()+n);
    t.erase(unique(t.begin(),t.begin()+n),t.begin()+n);
    for(int i=0;i<n;i++) a[i]=lower_bound(t.begin(),t.begin()+n,a[i])-t.begin();
    //
    int st,ed;
    for(int i=0;i<m;i++){
        cin>>st>>ed;
        st--; ed--;
        q.push_back({i,st,ed});
    }
    sort(q.begin(),q.end());
    st=q[0].st,ed=q[0].ed;
    int r=0;
    for(int i=st;i<=ed;i++){
        c[a[i]]++;
        if(c[a[i]]==2) r++;
    }
    res[q[0].idx]=r;
    for(int i=1;i<m;i++){
        while(st<q[i].st){
            if(c[a[st]]==2) r--;
            c[a[st]]--;
            if(c[a[st]]==2) r++;
            st++;
        }
        while(st>q[i].st){
            st--;
            if(c[a[st]]==2) r--;
            c[a[st]]++;
            if(c[a[st]]==2) r++;
        }
        while(ed<q[i].ed){
            ed++;
            if(c[a[ed]]==2) r--;
            c[a[ed]]++;
            if(c[a[ed]]==2) r++;
        }
        while(ed>q[i].ed){
            if(c[a[ed]]==2) r--;
            c[a[ed]]--;
            if(c[a[ed]]==2) r++;
            ed--;
        }
        res[q[i].idx]=r;
    }
    for(int i=0;i<m;i++) cout<<res[i]<<'\n';
}

seungwuk98 2년 전 1

문제점이 여러가지가 있습니다.

25번째 줄에서 unique를 써서 지웠으면, t의 길이가 달라집니다.

그런데 이분탐색 범위는 그대로 n개입니다. 배열의 숫자가 모두 1가지라면, 탐색하는 곳이 안좋은 메모리 접근이 되겠죠

따라서 25번째 erase를 end()까지 수행하고, 이분탐색의 범위를 end()까지 진행하거나

아예 정렬만하고 erase 코드를 지워버려도 상관없습니다. (어차피, lower_bound한 수는 유일합니다.)

그리고 38번째 줄에 if(c[a[i]]==2) r--; 가 필요합니다.

0000000000 2년 전 0

길이가 달라진다는 걸 잊고 있었네요; 감사합니다!

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

문제

문제

출처

ICPC

14413 Mo's 질문입니다.

0000000000 2년 전 0

seungwuk98 2년 전 1

0000000000 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말