Submission #919591

#	Time	Username	Problem	Language	Result	Execution time	Memory
919591		andrei_iorgulescu	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	1239 ms	80780 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int n,k,m,q;
int a[200005],b[200005];
pair<int,int> v[20][100005];///intervalul in care pot ajunge din i facand 2^j pasi
int aintl[400005],aintr[400005];
int aintll[20][400005],aintrr[20][400005];
int lg[100005];

void build(int nod,int l,int r)
{
    aintl[nod] = l;
    aintr[nod] = r;
    if (l != r)
    {
        int mij = (l + r) / 2;
        build(2 * nod,l,mij);
        build(2 * nod + 1,mij + 1,r);
    }
}

void buildb(int nod,int l,int r,int b)
{
    if (l == r)
    {
        aintl[nod] = v[b - 1][l].first;
        aintr[nod] = v[b - 1][l].second;
    }
    else
    {
        int mij = (l + r) / 2;
        buildb(2 * nod,l,mij,b);
        buildb(2 * nod + 1,mij + 1,r,b);
        aintl[nod] = min(aintl[2 * nod],aintl[2 * nod + 1]);
        aintr[nod] = max(aintr[2 * nod],aintr[2 * nod + 1]);
    }
}

void updater(int nod,int l,int r,int pos,int val)
{
    if (l == r)
        aintr[nod] = max(aintr[nod],val);
    else
    {
        int mij = (l + r) / 2;
        if (pos <= mij)
            updater(2 * nod,l,mij,pos,val);
        else
            updater(2 * nod + 1,mij + 1,r,pos,val);
        aintr[nod] = max(aintr[2 * nod],aintr[2 * nod + 1]);
    }
}

void updatel(int nod,int l,int r,int pos,int val)
{
    if (l == r)
        aintl[nod] = min(aintl[nod],val);
    else
    {
        int mij = (l + r) / 2;
        if (pos <= mij)
            updatel(2 * nod,l,mij,pos,val);
        else
            updatel(2 * nod + 1,mij + 1,r,pos,val);
        aintl[nod] = min(aintl[2 * nod],aintl[2 * nod + 1]);
    }
}

int queryr(int nod,int l,int r,int st,int dr)
{
    if (r < st or dr < l)
        return 0;
    if (st <= l and r <= dr)
        return aintr[nod];
    int mij = (l + r) / 2;
    return max(queryr(2 * nod,l,mij,st,dr),queryr(2 * nod + 1,mij + 1,r,st,dr));
}

int queryl(int nod,int l,int r,int st,int dr)
{
    if (r < st or dr < l)
        return n;
    if (st <= l and r <= dr)
        return aintl[nod];
    int mij = (l + r) / 2;
    return min(queryl(2 * nod,l,mij,st,dr),queryl(2 * nod + 1,mij + 1,r,st,dr));
}

void buildd(int nod,int l,int r,int b)
{
    if (l == r)
    {
        aintll[b][nod] = v[b][l].first;
        aintrr[b][nod] = v[b][l].second;
    }
    else
    {
        int mij = (l + r) / 2;
        buildd(2 * nod,l,mij,b);
        buildd(2 * nod + 1,mij + 1,r,b);
        aintll[b][nod] = min(aintll[b][2 * nod],aintll[b][2 * nod + 1]);
        aintrr[b][nod] = max(aintrr[b][2 * nod],aintrr[b][2 * nod + 1]);
    }
}

int queryll(int nod,int l,int r,int st,int dr,int b)
{
    if (r < st or dr < l)
        return n;
    if (st <= l and r <= dr)
        return aintll[b][nod];
    int mij = (l + r) / 2;
    return min(queryll(2 * nod,l,mij,st,dr,b),queryll(2 * nod + 1,mij + 1,r,st,dr,b));
}

int queryrr(int nod,int l,int r,int st,int dr,int b)
{
    if (r < st or dr < l)
        return 0;
    if (st <= l and r <= dr)
        return aintrr[b][nod];
    int mij = (l + r) / 2;
    return max(queryrr(2 * nod,l,mij,st,dr,b),queryrr(2 * nod + 1,mij + 1,r,st,dr,b));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k >> m;
    for (int i = 2; i <= n; i++)
        lg[i] = 1 + lg[i / 2];
    for (int i = 1; i <= m; i++)
        cin >> a[i] >> b[i];
    build(1,1,n);
    for (int i = 1; i <= m; i++)
    {
        if (a[i] < b[i])
            updater(1,1,n,a[i],b[i]);
        else
            updatel(1,1,n,a[i],b[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        v[0][i].first = queryl(1,1,n,i,min(n,i + k - 1));
        v[0][i].second = queryr(1,1,n,max(1,i - k + 1),i);
    }
    /*for (int i = 1; i <= n; i++)
        cout << v[0][i].first << ' ' << v[0][i].second << '\n';;
    cout << '\n';*/
    for (int b = 1; b <= lg[n]; b++)
    {
        ///v[b][i].first = min(v[b - 1][j].first), unde j in intervalul v[b - 1][i]
        ///v[b][i].second = max(v[b - 1][j].second), unde j in intervalul v[b - 1][i]
        buildb(1,1,n,b);
        for (int i = 1; i <= n; i++)
        {
            int intl = v[b - 1][i].first,intr = v[b - 1][i].second;
            //out << intl << ' ' << intr << "->";
            v[b][i].first = queryl(1,1,n,intl,intr);
            v[b][i].second = queryr(1,1,n,intl,intr);
        }
        /*for (int i = 1; i <= n; i++)
            cout << v[b][i].first << ' ' << v[b][i].second << '\n';;
        cout << '\n';*/
    }
    for (int b = 0; b <= lg[n]; b++)
    {
        buildd(1,1,n,b);
        //cout << "yup" << endl;
    }
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int s,f;
        cin >> s >> f;
        int intl = s,intr = s;
        int cost = 0;
        for (int jump = lg[n]; jump >= 0; jump--)
        {
            int newintl = queryll(1,1,n,intl,intr,jump);
            int newintr = queryrr(1,1,n,intl,intr,jump);
            if (f < newintl or f > newintr)
            {
                intl = newintl;
                intr = newintr;
                cost += (1 << jump);
            }
        }
        if (f < queryll(1,1,n,intl,intr,0) or f > queryrr(1,1,n,intl,intr,0))
            cout << -1 << '\n';
        else
            cout << cost + 1 << '\n';
    }
    return 0;
}

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