oj.uz

Submission #866794

# Submission time Handle Problem Language Result Execution time Memory
866794 2023-10-27T05:42:05 Z sleepntsheep Osumnjičeni (COCI21_osumnjiceni) C++17
10 / 110
 318 ms 11020 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 10960 KB Output is correct
2 Correct 284 ms 10992 KB Output is correct
3 Correct 284 ms 10968 KB Output is correct
4 Correct 284 ms 10968 KB Output is correct
5 Correct 303 ms 10956 KB Output is correct
6 Correct 94 ms 10968 KB Output is correct
7 Correct 100 ms 10968 KB Output is correct
8 Correct 103 ms 10956 KB Output is correct
9 Correct 110 ms 11000 KB Output is correct
10 Correct 106 ms 10960 KB Output is correct
11 Correct 189 ms 10956 KB Output is correct
12 Correct 194 ms 11016 KB Output is correct
13 Correct 178 ms 10960 KB Output is correct
14 Correct 197 ms 10956 KB Output is correct
15 Correct 186 ms 10968 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 97 ms 11020 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 8796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 8796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 318 ms 10956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 10960 KB Output is correct
2 Correct 284 ms 10992 KB Output is correct
3 Correct 284 ms 10968 KB Output is correct
4 Correct 284 ms 10968 KB Output is correct
5 Correct 303 ms 10956 KB Output is correct
6 Correct 94 ms 10968 KB Output is correct
7 Correct 100 ms 10968 KB Output is correct
8 Correct 103 ms 10956 KB Output is correct
9 Correct 110 ms 11000 KB Output is correct
10 Correct 106 ms 10960 KB Output is correct
11 Correct 189 ms 10956 KB Output is correct
12 Correct 194 ms 11016 KB Output is correct
13 Correct 178 ms 10960 KB Output is correct
14 Correct 197 ms 10956 KB Output is correct
15 Correct 186 ms 10968 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 97 ms 11020 KB Output is correct
18 Incorrect 14 ms 8796 KB Output isn't correct
19 Halted 0 ms 0 KB -