oj.uz

Submission #850194

# Submission time Handle Problem Language Result Execution time Memory
850194 2023-09-16T02:03:29 Z 12345678 Railway Trip 2 (JOI22_ho_t4) C++17
62 / 100
 850 ms 72292 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=18;
int n, k, m, a, b, q, s, t, fmx[nx], fmn[nx];
bool vsmx[nx], vsmn[nx];
vector<pair<int, int>> mx[nx], mn[nx];
priority_queue<pair<int, int>> pqmx;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pqmn;

struct segtree
{
    pair<int, int> d[4*nx];
    void init(int l, int r, int i)
    {
        if (l==r) return void(d[i]=make_pair(i, i));
        int md=(l+r)/2;
        init(l, md, 2*i);
        init(md+1, r, 2*i);
        d[i]=make_pair(l, r);
    }
    void update(int l, int r, int i, int idx, pair<int, int> p)
    {
        if (r<idx||idx<l) return;
        if (l==r) return void(d[i]=p);
        int md=(l+r)/2;
        update(l, md, 2*i, idx, p);
        update(md+1, r, 2*i+1, idx, p);
        d[i].first=min(d[2*i].first, d[2*i+1].first);
        d[i].second=max(d[2*i].second, d[2*i+1].second);
    }
    pair<int, int> query(int l, int r, int i, int ql, int qr)
    {
        if (r<ql||qr<l) return make_pair(INT_MAX, -INT_MAX);
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        pair<int, int> pl=query(l, md, 2*i, ql, qr), pr=query(md+1, r, 2*i+1, ql, qr);
        return make_pair(min(pl.first, pr.first), max(pl.second, pr.second));
    }
} st[kx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k>>m;
    for (int i=1; i<=m; i++) 
    {
        cin>>a>>b;
        if (a<b) mx[a].push_back({i, b}), mx[min(a+k, b+1)].push_back({-i, b});
        else mn[a].push_back({i, b}), mn[max(a-k, b-1)].push_back({-i, b});
    }
    for (int i=1; i<=n; i++)
    {
        for (auto [x, y]:mx[i])
        {
            if (x>0) pqmx.push({y, x});
            else vsmx[-x]=1;
        }
        while (!pqmx.empty()&&vsmx[pqmx.top().second]) pqmx.pop();
        fmx[i]=pqmx.empty()?i:pqmx.top().first;
    }
    for (int i=n; i>=1; i--)
    {
        for (auto [x, y]:mn[i])
        {
            if (x>0) pqmn.push({y, x});
            else vsmn[-x]=1;
        }
        while (!pqmn.empty()&&vsmn[pqmn.top().second]) pqmn.pop();
        fmn[i]=pqmn.empty()?i:pqmn.top().first;
    }
    for (int i=0; i<kx; i++) st[i].init(1, n, 1);
    for (int i=1; i<=n; i++) st[0].update(1, n, 1, i, make_pair(fmn[i], fmx[i]));
    for (int i=1; i<kx; i++) 
    {
        for (int j=1; j<=n; j++) 
        {
            pair<int, int> q1=st[i-1].query(1, n, 1, j, j);
            st[i].update(1, n, 1, j, st[i-1].query(1, n, 1, q1.first, q1.second));
        }
    }
    cin>>q;
    while (q--)
    {
        cin>>s>>t;
        int sm(0);
        pair<int, int> l=make_pair(s, s);
        for (int i=kx-1; i>=0; i--)
        {
            pair<int, int> nw=st[i].query(1, n, 1, l.first, l.second);
            if (t<nw.first||t>nw.second) sm+=(1<<i), l=nw;
        }
        if (sm>=n) cout<<-1<<'\n';
        else cout<<sm+1<<'\n';
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41304 KB Output is correct
2 Correct 6 ms 41304 KB Output is correct
3 Correct 6 ms 41308 KB Output is correct
4 Correct 6 ms 41304 KB Output is correct
5 Correct 6 ms 41304 KB Output is correct
6 Correct 6 ms 41304 KB Output is correct
7 Correct 6 ms 41304 KB Output is correct
8 Correct 6 ms 41304 KB Output is correct
9 Correct 6 ms 41304 KB Output is correct
10 Correct 5 ms 41492 KB Output is correct
11 Correct 6 ms 41304 KB Output is correct
12 Correct 6 ms 41304 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41304 KB Output is correct
2 Correct 6 ms 41304 KB Output is correct
3 Correct 6 ms 41308 KB Output is correct
4 Correct 6 ms 41304 KB Output is correct
5 Correct 6 ms 41304 KB Output is correct
6 Correct 6 ms 41304 KB Output is correct
7 Correct 6 ms 41304 KB Output is correct
8 Correct 6 ms 41304 KB Output is correct
9 Correct 6 ms 41304 KB Output is correct
10 Correct 5 ms 41492 KB Output is correct
11 Correct 6 ms 41304 KB Output is correct
12 Correct 6 ms 41304 KB Output is correct
13 Correct 16 ms 41560 KB Output is correct
14 Correct 15 ms 41560 KB Output is correct
15 Correct 12 ms 41560 KB Output is correct
16 Correct 13 ms 41560 KB Output is correct
17 Correct 17 ms 41816 KB Output is correct
18 Correct 11 ms 41560 KB Output is correct
19 Correct 13 ms 41560 KB Output is correct
20 Correct 13 ms 41560 KB Output is correct
21 Correct 10 ms 41560 KB Output is correct
22 Correct 14 ms 41564 KB Output is correct
23 Correct 14 ms 41560 KB Output is correct
24 Correct 15 ms 41564 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 65416 KB Output is correct
2 Correct 605 ms 65396 KB Output is correct
3 Correct 643 ms 65568 KB Output is correct
4 Correct 587 ms 65508 KB Output is correct
5 Correct 396 ms 71220 KB Output is correct
6 Correct 613 ms 69572 KB Output is correct
7 Correct 379 ms 72028 KB Output is correct
8 Correct 352 ms 67412 KB Output is correct
9 Correct 358 ms 67668 KB Output is correct
10 Correct 554 ms 71056 KB Output is correct
11 Correct 568 ms 70624 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 68208 KB Output is correct
2 Correct 626 ms 70480 KB Output is correct
3 Correct 768 ms 69920 KB Output is correct
4 Correct 472 ms 72292 KB Output is correct
5 Correct 470 ms 71712 KB Output is correct
6 Correct 475 ms 71268 KB Output is correct
7 Incorrect 675 ms 69864 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 70672 KB Output is correct
2 Correct 850 ms 66916 KB Output is correct
3 Correct 827 ms 64984 KB Output is correct
4 Correct 767 ms 63660 KB Output is correct
5 Correct 666 ms 62788 KB Output is correct
6 Correct 700 ms 62556 KB Output is correct
7 Correct 583 ms 67320 KB Output is correct
8 Correct 6 ms 41304 KB Output is correct
9 Correct 14 ms 41560 KB Output is correct
10 Correct 539 ms 70240 KB Output is correct
11 Correct 612 ms 70508 KB Output is correct
12 Correct 601 ms 70336 KB Output is correct
13 Correct 612 ms 70600 KB Output is correct
14 Correct 6 ms 41560 KB Output is correct
15 Correct 15 ms 41616 KB Output is correct
16 Correct 600 ms 68780 KB Output is correct
17 Correct 792 ms 71076 KB Output is correct
18 Correct 763 ms 70524 KB Output is correct
19 Correct 740 ms 70424 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41304 KB Output is correct
2 Correct 6 ms 41304 KB Output is correct
3 Correct 6 ms 41308 KB Output is correct
4 Correct 6 ms 41304 KB Output is correct
5 Correct 6 ms 41304 KB Output is correct
6 Correct 6 ms 41304 KB Output is correct
7 Correct 6 ms 41304 KB Output is correct
8 Correct 6 ms 41304 KB Output is correct
9 Correct 6 ms 41304 KB Output is correct
10 Correct 5 ms 41492 KB Output is correct
11 Correct 6 ms 41304 KB Output is correct
12 Correct 6 ms 41304 KB Output is correct
13 Correct 16 ms 41560 KB Output is correct
14 Correct 15 ms 41560 KB Output is correct
15 Correct 12 ms 41560 KB Output is correct
16 Correct 13 ms 41560 KB Output is correct
17 Correct 17 ms 41816 KB Output is correct
18 Correct 11 ms 41560 KB Output is correct
19 Correct 13 ms 41560 KB Output is correct
20 Correct 13 ms 41560 KB Output is correct
21 Correct 10 ms 41560 KB Output is correct
22 Correct 14 ms 41564 KB Output is correct
23 Correct 14 ms 41560 KB Output is correct
24 Correct 15 ms 41564 KB Output is correct
25 Correct 635 ms 65416 KB Output is correct
26 Correct 605 ms 65396 KB Output is correct
27 Correct 643 ms 65568 KB Output is correct
28 Correct 587 ms 65508 KB Output is correct
29 Correct 396 ms 71220 KB Output is correct
30 Correct 613 ms 69572 KB Output is correct
31 Correct 379 ms 72028 KB Output is correct
32 Correct 352 ms 67412 KB Output is correct
33 Correct 358 ms 67668 KB Output is correct
34 Correct 554 ms 71056 KB Output is correct
35 Correct 568 ms 70624 KB Output is correct
36 Correct 616 ms 68208 KB Output is correct
37 Correct 626 ms 70480 KB Output is correct
38 Correct 768 ms 69920 KB Output is correct
39 Correct 472 ms 72292 KB Output is correct
40 Correct 470 ms 71712 KB Output is correct
41 Correct 475 ms 71268 KB Output is correct
42 Incorrect 675 ms 69864 KB Output isn't correct
43 Halted 0 ms 0 KB -