Submission #890183

#	Time	Username	Problem	Language	Result	Execution time	Memory
890183		ace5	Railway Trip 2 (JOI22_ho_t4)	C++17	8 / 100	290 ms	33236 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100001,maxlogn = 17;
const int sqr = 200;

int st[4][maxlogn][maxn];
int maxst[maxn];
int l[maxn];
int r[maxn];

int MIN1(int l,int r)
{
    int ts = maxst[r-l+1];
    return min(st[0][ts][l],st[0][ts][r-(1<<ts)+1]);
}
int MAX1(int l,int r)
{
    int ts = maxst[r-l+1];
    return max(st[1][ts][l],st[1][ts][r-(1<<ts)+1]);
}
int MINs(int l,int r)
{
    int ts = maxst[r-l+1];
    return min(st[2][ts][l],st[2][ts][r-(1<<ts)+1]);
}
int MAXs(int l,int r)
{
    int ts = maxst[r-l+1];
    return max(st[3][ts][l],st[3][ts][r-(1<<ts)+1]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    int m;
    cin >> m;
    vector<int> tl(n),tr(n);
    for(int i = 0;i < n;++i)
    {
        tl[i] = i;
        tr[i] = i;
    }
    for(int i = 0;i < m;++i)
    {
        int lx,rx;
        cin >> lx >> rx;
        lx--;
        rx--;
        if(lx > rx)
        {
            tl[lx] = min(tl[lx],rx);
        }
        else
        {
            tr[lx] = max(tr[lx],rx);
        }
    }
    multiset<int> cc;
    for(int i = n-1;i >= 0;--i)
    {
        if(i+k < n)
        {
            cc.erase(cc.find(tl[i+k]));
        }
       // cout << tl[i] << ' ';
        cc.insert(tl[i]);
        l[i] = *cc.begin();
       // cout << l[i] << ' ';
    }
   // cout << "\n";
    cc.clear();
    for(int i = 0;i < n;++i)
    {
        if(i >= k)
        {
            cc.erase(cc.find(-tr[i-k]));
        }
        cc.insert(-tr[i]);
        r[i] = -(*cc.begin());
       // cout << r[i] << ' ';
    }
   // cout << "\n";
    int tst = 0;
    for(int j = 1;j < maxn;++j)
    {
        maxst[j] = tst;
        if((1<<(tst+1)) <= j+1)
            tst++;
    }
    for(int i = 0;i < maxlogn;++i)
    {
        for(int j = 0;j < n-(1<<i)+1;++j)
        {
            if(i == 0)
                st[0][i][j] = l[j];
            else
                st[0][i][j] = min(st[0][i-1][j],st[0][i-1][j+(1<<(i-1))]);
        }
    }
    for(int i = 0;i < maxlogn;++i)
    {
        for(int j = 0;j < n-(1<<i)+1;++j)
        {
            if(i == 0)
                st[1][i][j] = r[j];
            else
                st[1][i][j] = max(st[1][i-1][j],st[1][i-1][j+(1<<(i-1))]);
        }
    }
    for(int i = 0;i < sqr-1;++i)
    {
        for(int j = 0;j < n;++j)
        {
            int nl = MIN1(l[j],r[j]);
            int nr = MAX1(l[j],r[j]);
            l[j] = nl;
            r[j] = nr;
        }
    }
    for(int i = 0;i < maxlogn;++i)
    {
        for(int j = 0;j < n-(1<<i)+1;++j)
        {
            if(i == 0)
                st[2][i][j] = l[j];
            else
                st[2][i][j] = min(st[2][i-1][j],st[2][i-1][j+(1<<(i-1))]);
        }
    }
    for(int i = 0;i < maxlogn;++i)
    {
        for(int j = 0;j < n-(1<<i)+1;++j)
        {
            if(i == 0)
                st[3][i][j] = r[j];
            else
                st[3][i][j] = max(st[3][i-1][j],st[1][i-1][j+(1<<(i-1))]);
        }
    }
  //  cout << MIN1(1,1);
    int q;
    cin >> q;
    while(q--)
    {
        int s,t;
        cin >> s >> t;
        s--;
        t--;
        int ls = s,rs = s;
        int ans = 0;
        int y = 0;
        for(int j = 0;j < sqr;++j)
        {
            int nls = MINs(ls,rs);
            int nrs = MAXs(ls,rs);
            if(nls > t || nrs < t)
            {
                ls = nls;
                rs = nrs;
                ans += sqr;
            }
            else
            {
                y=  1;
                break;
            }
        }
        for(int j = 0;j < sqr;++j)
        {
            int nls = MIN1(ls,rs);
            int nrs = MAX1(ls,rs);
            if(nls > t || nrs < t)
            {
                ls = nls;
                rs = nrs;
                ans ++;
            }
            else
            {
                ans ++;
                y = 1;
                break;
            }
        }
        if(!y)
            cout << -1 << "\n";
        else
            cout << ans << "\n";
    }
    return 0;
}

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