백준 12016 : 라운드 로빈 스케쥴러

문제 링크

세그먼트 트리를 이용하여 해결하였다.

다른 사람들의 코드를 보면 펜윅 트리를 이용해서 끝난 작업의 수를 카운트해주어서 해결하였는데, 나도 비슷하게 세그먼트 트리를 이용하였지만, 문제에 나와있는 그대로 lazy propagation이용해서 시뮬레이션하듯이 해결하였다. 덕분에 코드도 엄청 더러워지고 시간도 걸렸지만.. 아무튼 일단 해결했다.

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

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int INF = 21 * 1e8;
const int MAX = 1e9;

vector<int> idxvec;
vector<pii> segtree;
vector<int> idxseg;
vector<int> lazy;
vector<pii> vec;

int n;

pii Init(int idx,int s,int e)
{
    if(s == e) return segtree[idx] = vec[s];

    int m = (s+e)/2;

    return segtree[idx] = min(Init(2*idx,s,m),Init(2*idx+1,m+1,e));
}

void Propagate(int idx,int s,int e)
{
    if(lazy[idx])
    {
        segtree[idx].first += lazy[idx];

        if(s != e)
        {
            lazy[2*idx] += lazy[idx];
            lazy[2*idx+1] += lazy[idx];
        }

        lazy[idx] = 0;
    }
}

void Update_range(int qs,int qe,int k,int idx,int s,int e)
{
    Propagate(idx,s,e);
    
    if(e < qs || qe < s) return;

    if(qs <= s && e <= qe)
    {
        lazy[idx] += k;
        Propagate(idx,s,e);

        return;
    }

    int m = (s+e)/2;

    Update_range(qs,qe,k,2*idx,s,m);
    Update_range(qs,qe,k,2*idx+1,m+1,e);

    segtree[idx] = min(segtree[2*idx],segtree[2*idx+1]);
}

pii Get(int qs,int qe,int idx,int s,int e)
{
    Propagate(idx,s,e);

    if(e < qs || qe < s) return {INF,0};

    if(qs <= s && e <= qe) return segtree[idx];

    int m = (s+e)/2;

    return min(Get(qs,qe,2*idx,s,m),Get(qs,qe,2*idx+1,m+1,e));
}

int idxInit(int idx,int s,int e)
{
    if(s == e) return idxseg[idx] = idxvec[s];

    int m = (s+e)/2;

    return idxseg[idx] = idxInit(2*idx,s,m) + idxInit(2*idx+1,m+1,e);
}

int idxUpdate(int newidx,int k,int idx,int s,int e)
{
    if(s > newidx || e < newidx) return idxseg[idx];

    if(s == e) return idxseg[idx] += k;

    int m = (s+e)/2;

    return idxseg[idx] = idxUpdate(newidx,k,2*idx,s,m) + idxUpdate(newidx,k,2*idx+1,m+1,e);
}

int idxGet(int qs,int qe,int idx,int s,int e)
{
    if(e < qs || qe < s) return 0;

    if(qs <= s && e <= qe) return idxseg[idx];

    int m = (s+e)/2;

    return idxGet(qs,qe,2*idx,s,m) + idxGet(qs,qe,2*idx+1,m+1,e);
}

void Update_range(int qs,int qe,int k)
{
    Update_range(qs,qe,k,1,0,n-1);
}

pii Get(int qs,int qe)
{
    return Get(qs,qe,1,0,n-1);
}

int idxUpdate(int newidx,int k)
{
    return idxUpdate(newidx,k,1,0,n-1);
}

int idxGet(int qs,int qe)
{
    return idxGet(qs,qe,1,0,n-1);
}

int main()
{
    scanf("%d",&n);

    for(int i =0;i<n;i++)
    {
        int num;
        scanf("%d",&num);

        vec.push_back({num,i});
    }
    
    idxvec = vector<int>(n,1);
    idxseg = vector<int>(4*n);
    segtree = vector<pii>(4*n);
    lazy = vector<int>(4*n,0);

    Init(1,0,n-1);
    idxInit(1,0,n-1);

    ll sofar = 0;
    int cnt = n;
    vector<ll> ans(n);
    while(cnt > 0)
    {
        int cyclecnt = Get(0,n-1).first;

        if(cyclecnt > 0) sofar += 1LL * cnt * (cyclecnt-1);
        Update_range(0,n-1,-cyclecnt);


        int prev = 0;
        pii curmin = Get(0,n-1);
        while(curmin.first == 0)
        {    
            sofar += idxGet(prev,curmin.second);
            
            ans[curmin.second] = sofar;

            
            prev = curmin.second;
            idxUpdate(curmin.second,-1);
            Update_range(curmin.second,curmin.second,INF);
            cnt--;

            curmin = Get(0,n-1);
        }

        sofar += idxGet(prev,n-1);
    }

    for(auto elem : ans)
    {
        printf("%lld\n",elem);
    }
    return 0;
}
​