제출 #597587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
597587		boris_mihov	Event Hopping (BOI22_events)	C++14	55 / 100	123 ms	18984 KiB

events

#include <algorithm>
#include <iostream>
#include <numeric>

const int MAXN = 100000 + 10;
const int MAXLOG = 17;
const int INF = 1e9 + 10;

struct Event
{
    int s, e;
    inline friend bool operator < (Event a, Event b)
    {
        return a.s < b.s || (a.s == b.s && a.e < b.e);
    }
} ev[MAXN];

int n, q;
int getLog[MAXN];
int rmq[MAXLOG][MAXN];
int lift[MAXLOG][MAXN];
int perm[MAXN], newNum[MAXN];

int cmp(int x, int y)
{
    if (ev[x].e >= ev[y].e) return x;
    return y;
}

void buildRMQ()
{
    std::iota(rmq[0]+1, rmq[0]+1+n, 1);
    for (int log = 1 ; (1 << log) <= n ; ++log)
    {
        for (int i = 1 ; i + (1 << log) - 1 <= n ; ++i)
        {
            rmq[log][i] = cmp(rmq[log-1][i], rmq[log-1][i + (1 << log-1)]);
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        getLog[i] = getLog[i-1];
        if ((1 << getLog[i]+1) < i) ++getLog[i];
    }
}

int upperBinSearch(int value)
{
    int l = 0, r = n+1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (ev[mid].s <= value) l = mid;
        else r = mid;
    }

    return l;
}

int lowerBinSearch(int idx)
{
    int l = 0, r = n, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (mid <= idx || ev[mid].s < ev[idx].s) l = mid;
        else r = mid;
    }

    return r;
}

int findMaximum(int l, int r)
{
    int log = getLog[r-l+1];
    return cmp(rmq[log][l], rmq[log][r - (1 << log) + 1]);
}

void buildLift()
{
    for (int log = 1 ; (1 << log) <= n ; ++log)
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            lift[log][i] = lift[log-1][lift[log-1][i]];
        }
    }
}

int binaryLifting(int from, int value)
{
    if (ev[from].s > value) return -1;
    int ans = 1 + (ev[from].e < value);
    for (int log = MAXLOG-1 ; log >= 0 ; --log)
    {
        if (lift[log][from] == 0) continue;
        if (ev[lift[log][from]].e < value)
        {
            ans += (1 << log);
            from = lift[log][from];   
        }
    }

    if (ev[lift[0][from]].e < value) return -1;
    else return ans;
}

void solve()
{
    std::iota(perm+1, perm+1+n, 1);
    std::sort(perm+1, perm+1+n, [&](int x, int y)
    {
        return ev[x] < ev[y];
    });

    for (int i = 1 ; i <= n ; ++i)
    {
        newNum[perm[i]] = i;
    }

    std::sort(ev+1, ev+1+n);
    buildRMQ();

    for (int i = 1 ; i <= n ; ++i)
    {
        int from = lowerBinSearch(i);
        int to = upperBinSearch(ev[i].e);
        if (i+1 <= from && from <= to)
        {
            int jump = findMaximum(from, to);
            lift[0][i] = jump;
            if (i == jump) lift[0][i] = 0;
        }
    }

    buildLift();
    for (int i = 1 ; i <= q ; ++i)
    {
        int st, en;
        std::cin >> st >> en; 
        std::swap(st, en);
       
        if (st == en)
        {
            std::cout << 0 << '\n';
            continue;
        }

        st = newNum[st];
        en = ev[newNum[en]].s;
        int res = binaryLifting(st, en);
        if (res == -1) std::cout << "impossible\n";
        else std::cout << res << '\n';
    }
}

void read()
{
    std::cin >> n >> q;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> ev[i].s >> ev[i].e;
        ev[i].s = INF - ev[i].s;
        ev[i].e = INF - ev[i].e;
        std::swap(ev[i].s, ev[i].e);
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

events.cpp: In function 'void buildRMQ()':
events.cpp:37:70: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   37 |             rmq[log][i] = cmp(rmq[log-1][i], rmq[log-1][i + (1 << log-1)]);
      |                                                                   ~~~^~
events.cpp:44:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   44 |         if ((1 << getLog[i]+1) < i) ++getLog[i];
      |                   ~~~~~~~~~^~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30