본문 바로가기

알고리즘 관련/BOJ

BOJ)13274 수열

문제: icpc.me/13274


정렬 된 수열에서 쿼리를 처리하는 문제이다.


쿼리 l r x 는 l~r 구간의 원소에 x를 더해준 뒤 다시 정렬하는 쿼리이다.


n이 10만이고 쿼리가 1000개 인데 매번 퀵소트를 실행해주면 1억xlog10만 이므로 1초의 제한 시간에 간당간당한 느낌이다.


따라서 좀 더 빠른 소팅 방법이 필요한데,


정렬 된 구간에서 l~r에 x를 더하게 되면,  l~r의 구간은 오름차순을 유지할 것이며, 전체의 구간에서 l~r의 구간을 제외한 구간 역시 오름차순을 유지할 것이다.


이렇게 정렬 된 두 구간에서 서로 가장 앞 원소를 비교하며 insertion sort를 하면 소팅을 O(N)의 시간에 해결할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int n,k,x,y;
ll xx,z;
vector<ll> vt,t;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%lld",&xx);
        vt.push_back(xx);
    }
    sort(vt.begin(),vt.end());
    t.assign(n,0);
    while(k--){
        scanf("%d%d%lld",&x,&y,&z);
        int it=x-1;
        int idx=0;
        for(int i=0;i<x-1;i++){
            while(it!=y&&vt[it]+z<=vt[i])
                t[idx++]=vt[it++]+z;
            t[idx++]=vt[i];
        }
        for(int i=y;i<n;i++){
            while(it!=y&&vt[it]+z<=vt[i])
                t[idx++]=vt[it++]+z;
            t[idx++]=vt[i];
        }
        while(it!=y)
            t[idx++]=vt[it++]+z;
        for(int i=0;i<n;i++)
            vt[i]=t[i];
    }
    for(auto next:vt)printf("%lld ",next);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14400 편의점2  (0) 2018.07.05
BOJ)15745 Snow Boots  (0) 2018.07.03
BOJ)15589 Lifeguards (Silver)  (0) 2018.06.26
BOJ)14965 Lozinke  (0) 2018.06.26
BOJ)11964 Fruit Feast  (0) 2018.06.25