제출 #1353038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1353038		Alex1298	Equalmex (CEOI25_equalmex)	C++20	4 / 100	2096 ms	26660 KiB

equalmex

#include <iostream>
#include <vector>

using namespace std;

struct Node
{
    int minpoz;
    int st, dr;
};

int n, q;
int cnt;
int v[600005];
pair<int, int> qs[600005];
Node pool[5000005];
int root[600005];

void update(int cur, int prev, int left, int right, int poz, int val)
{
    if(left == right)
    {
        pool[cur].minpoz = val;
        return;
    }

    int mij = (left + right) / 2;
    if(poz <= mij)
    {
        cnt++;
        pool[cur].st = cnt;
        pool[pool[cur].st] = pool[pool[prev].st];

        pool[cur].dr = pool[prev].dr;

        update(pool[cur].st, pool[prev].st, left, mij, poz, val);
    }
    else
    {
        cnt++;
        pool[cur].dr = cnt;
        pool[pool[cur].dr] = pool[pool[prev].dr];

        pool[cur].st = pool[prev].st;

        update(pool[cur].dr, pool[prev].dr, mij+1, right, poz, val);
    }

    pool[cur].minpoz = min(pool[pool[cur].st].minpoz, pool[pool[cur].dr].minpoz);
}

int find_mex(int node, int left, int right, int st)
{
    if(left == right)
    {
        return left;
    }

    int mij = (left + right) / 2;
    if(pool[pool[node].st].minpoz < st)
    {
        return find_mex(pool[node].st, left, mij, st);
    }
    else
    {
        return find_mex(pool[node].dr, mij+1, right, st);
    }
}

int query(int node, int left, int right, int qleft, int qright)
{
    if(qright < left || right < qleft)
    {
        return n + 1;
    }

    if(qleft <= left && right <= qright)
    {
        return pool[node].minpoz;
    }

    int mij = (left + right) / 2;
    return min(query(pool[node].st, left, mij, qleft, qright),
               query(pool[node].dr, mij+1, right, qleft, qright));
}

std::vector<int> solve(int N, std::vector<int> &init, int Q, std::vector<std::pair<int, int>> &initqs)
{
    n = N;
    q = Q;

    for(int i = 0; i<n; i++)
    {
        v[i + 1] = init[i];
    }
    for(int i = 0; i<q; i++)
    {
        qs[i + 1] = initqs[i];
        qs[i + 1].first++;
        qs[i + 1].second++;
    }

    for(int i = 1; i<=n; i++)
    {
        cnt++;
        root[i] = cnt;

        update(root[i], root[i - 1], 1, 4e5, v[i], i);
    }

    vector<int> rez;
    for(int i = 1; i<=q; i++)
    {
        int mex = find_mex(root[qs[i].second], 1, 4e5, qs[i].first);
        if(mex == 1)
        {
            rez.push_back(qs[i].second - qs[i].first + 1);
            continue;
        }

        int ans = 0;
        int cur = qs[i].second;
        while(cur >= qs[i].first)
        {
            int nxt = query(root[cur], 1, 4e5, 1, mex - 1);
            if(nxt < qs[i].first)
            {
                break;
            }

            ans++;
            cur = nxt;
        }

        rez.push_back(ans);
    }

    return rez;
}

• 서브태스크 1: 4 / 4
• 서브태스크 2: 0 / 6
• 서브태스크 3: 0 / 17
• 서브태스크 4: 0 / 10
• 서브태스크 5: 0 / 30
• 서브태스크 6: 0 / 33