백준 10124 - Couriers

김성지·2022년 11월 24일
0

백준

목록 보기
5/19

문제링크 : https://www.acmicpc.net/problem/10124

mo`s 추천문제에 있길래
https://www.acmicpc.net/problem/2912
이거랑 똑같이 풀리나해서 했는데
N하고 Q가 500000 이였다...

첨엔 그냥 백설공주와 난쟁이 저 문제랑 똑같이 제출했었다
sqrt decompositon+오프라인쿼리 로 접근했는데 찾아보니깐 이 풀이는

O((N+Q) x N^1/2 + Q x MAXN(종류의 최대치)) 이라서 터진다

시간초과 코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int N,M;int sqrtN;int table[500001];
int MAXN = 0;
vector<int> v;vector<int> ret;
struct query
{
    int idx,i,j;
};
bool cmp(query &a,query &b){
    if(a.i/sqrtN!=b.i/sqrtN) return a.i<b.i;
    return a.j<b.j;
}
vector<query> q;
void find(int idx,int k){
    for(int i=1;i<=MAXN;i++){
        if(table[i]>k){
            ret[idx]=i;
            return ;
        }
    }
    ret[idx]=0;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>N>>M;sqrtN=(int)sqrt(N);
    for(int i=0;i<N;i++){
        int a;cin>>a;
        v.push_back(a);
        MAXN = max(MAXN,a);
    }
    for(int i=0;i<M;i++){
        int a,b;cin>>a>>b;
        q.push_back({i,a-1,b-1});
    }
    sort(q.begin(),q.end(),cmp);
    int s = q[0].i; int e = q[0].j;
    int ans = 0;
    ret.resize(q.size());
    int ite = (e-s+1)/2;
    for(int i=s;i<=e;i++){
        table[v[i]]++;
    }
    find(q[0].idx,ite);
    for(int x=1;x<M;x++){
        while(s<q[x].i){
            table[v[s++]]--;
        }   
        while(s>q[x].i){
            table[v[--s]]++;
        }
        while(e<q[x].j){
            table[v[++e]]++;
        }
        while(e>q[x].j){
            table[v[e--]]--;
        }
        ite = (e-s+1)/2;
        find(q[x].idx,ite);
    }
    for(int i=0;i<M;i++){
        cout<<ret[i]<<"\n";
    }
}

AC 받은 풀이
세그트리

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int N,M;int MAXN = 0;
vector<int> v; vector<int> idx[500001];
int segtree[500001*4];
void init(int s,int e,int node){
    if(s==e){
        segtree[node]=v[s]; return;
    }
    int mid = (s+e)/2;
    init(s,mid,node*2);
    init(mid+1,e,node*2+1);
    int ll = segtree[node*2];
    int cnt = upper_bound(idx[ll].begin(),idx[ll].end(),e)-
    lower_bound(idx[ll].begin(),idx[ll].end(),s)+1;
    if(cnt>(e-s+1)/2){
        segtree[node]=ll;return;
    }
    int rr = segtree[node*2+1];
    cnt = upper_bound(idx[rr].begin(),idx[rr].end(),e)-
    lower_bound(idx[rr].begin(),idx[rr].end(),s)+1;
    if(cnt>(e-s+1)/2){
        segtree[node]=rr;return ;
    }
    segtree[node]=0;
}
int query(int s,int e,int node,int l,int r){
    if(s>r||e<l) return 0;
    if(l<=s&&e<=r){
        int cnt = upper_bound(idx[segtree[node]].begin(),idx[segtree[node]].end(),r)-
        lower_bound(idx[segtree[node]].begin(),idx[segtree[node]].end(),l);
        if(cnt>(r-l+1)/2){
            return segtree[node];
        }
        return 0;
    }
    int mid = (s+e)/2;
    int left = query(s,mid,node*2,l,r);
    int right = query(mid+1,e,node*2+1,l,r);
    if(left>0) return left;
    if(right>0) return right;
    return 0;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>N>>M;
    for(int i=0;i<N;i++){
        int a;cin>>a;
        v.push_back(a);
        idx[a].push_back(i);
        MAXN = max(MAXN,a);
    }
    for(int i=1;i<=MAXN;i++){
        sort(idx[i].begin(),idx[i].end());
    }
    init(0,N-1,1);
    for(int i=0;i<M;i++){
        int a,b;cin>>a>>b;
        cout<<query(0,N-1,1,a-1,b-1)<<"\n";
    }
}

idx 배열, 이걸로 이분탐색하면서 트리값 채워주면 된다.

0개의 댓글