Submission #866794

#	Time	Username	Problem	Language	Result	Execution time	Memory
866794		sleepntsheep	Osumnjičeni (COCI21_osumnjiceni)	C++17	10 / 110	318 ms	11020 KiB

Main

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
using ll = long long;
#define N 200005

int n, q, dep[N], jmp[N], par[N], t[N<<2], lz[N<<2];
pair<int, int> a[N];

void compress()
{
    vector<int> C;
    for (int i = 0; i < n; ++i) C.push_back(a[i].first), C.push_back(a[i].second);
    sort(ALL(C));
    C.erase(unique(ALL(C)), C.end());
    for (int i = 0; i < n; ++i) a[i].first = lower_bound(ALL(C), a[i].first) - C.begin(),
        a[i].second = lower_bound(ALL(C), a[i].second) - C.begin();
}

void push(int v, int l, int r)
{
    if (lz[v] < 1e9)
    {
        t[v] = lz[v];
        int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2;
        if (l != r) lz[vl] = lz[v], lz[vr] = lz[v];
        lz[v] = 1e9;
    }
}

void update(int v, int l, int r, int x, int y, int k)
{
    push(v, l, r);
    if (r < x || y < l) return;
    if (x <= l && r <= y) { lz[v] = k; push(v, l, r); return; }
    int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2;
    update(vl, l, m, x, y, k), update(vr, m+1, r, x, y, k);
    t[v] = min(t[vl], t[vr]);
}

int query(int v, int l, int r, int x, int y)
{
    push(v, l, r);
    if (r < x || y < l) return 1e9+86;
    if (x <= l && r <= y) return t[v];
    int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2;
    return min(query(vl, l, m, x, y), query(vr, m+1, r, x, y));
}

void init()
{
    memset(t, 63, sizeof t), memset(lz, 63, sizeof lz);
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;

    compress();
    par[n] = n; dep[n] = 0; jmp[n] = n;

    for (int i = n; i--;)
    {
        par[i] = query(0, 0, 2*n, a[i].first, a[i].second);
        update(0, 0, 2*n, a[i].first, a[i].second, i);
        par[i] = min(par[i], par[i+1]);
        dep[i] = dep[par[i]] + 1;
        if (dep[par[i]] - dep[jmp[par[i]]] == dep[jmp[par[i]]] - dep[jmp[jmp[par[i]]]])
            jmp[i] = jmp[jmp[par[i]]];
        else jmp[i] = par[i];
    }
}

void answer()
{
    cin >> q;
    for (int x, y, z; q--;)
    {
        cin >> x >> y, --x, --y, z = dep[x];
        for (; x <= y;)
        {
            if (dep[jmp[x]] <= dep[y]) x = jmp[x];
            else x = par[x];
        }
        cout << z - dep[x]  << '\n';
    }
}

int main()
{
    init();
    answer();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50