Submission #850217

#	Time	Username	Problem	Language	Result	Execution time	Memory
850217		12345678	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	879 ms	73604 KiB

Main

#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[2*nx], vsmn[2*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 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_MIN);
        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>nx) cout<<-1<<'\n';
        else cout<<sm+1<<'\n';
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13