oj.uz

Submission #866793

# Submission time Handle Problem Language Result Execution time Memory
866793 2023-10-27T05:38:46 Z sleepntsheep Osumnjičeni (COCI21_osumnjiceni) C++17
10 / 110
 315 ms 14800 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 = 0;
        for (; x <= y;)
        {
            if (dep[jmp[x]] <= dep[y]) z += dep[x] - dep[jmp[x]], x = jmp[x];
            else z += dep[x] - dep[par[x]], x = par[x];
        }
        cout << z << '\n';
    }
}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 11012 KB Output is correct
2 Correct 282 ms 14540 KB Output is correct
3 Correct 289 ms 14444 KB Output is correct
4 Correct 290 ms 14572 KB Output is correct
5 Correct 301 ms 14800 KB Output is correct
6 Correct 92 ms 14432 KB Output is correct
7 Correct 106 ms 14544 KB Output is correct
8 Correct 104 ms 14544 KB Output is correct
9 Correct 110 ms 14544 KB Output is correct
10 Correct 108 ms 14436 KB Output is correct
11 Correct 193 ms 14032 KB Output is correct
12 Correct 178 ms 14032 KB Output is correct
13 Correct 178 ms 13816 KB Output is correct
14 Correct 193 ms 14032 KB Output is correct
15 Correct 186 ms 13924 KB Output is correct
16 Correct 2 ms 8536 KB Output is correct
17 Correct 98 ms 14568 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 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 13 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 315 ms 10960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 11012 KB Output is correct
2 Correct 282 ms 14540 KB Output is correct
3 Correct 289 ms 14444 KB Output is correct
4 Correct 290 ms 14572 KB Output is correct
5 Correct 301 ms 14800 KB Output is correct
6 Correct 92 ms 14432 KB Output is correct
7 Correct 106 ms 14544 KB Output is correct
8 Correct 104 ms 14544 KB Output is correct
9 Correct 110 ms 14544 KB Output is correct
10 Correct 108 ms 14436 KB Output is correct
11 Correct 193 ms 14032 KB Output is correct
12 Correct 178 ms 14032 KB Output is correct
13 Correct 178 ms 13816 KB Output is correct
14 Correct 193 ms 14032 KB Output is correct
15 Correct 186 ms 13924 KB Output is correct
16 Correct 2 ms 8536 KB Output is correct
17 Correct 98 ms 14568 KB Output is correct
18 Incorrect 13 ms 8796 KB Output isn't correct
19 Halted 0 ms 0 KB -