Submission #824543

#	Time	Username	Problem	Language	Result	Execution time	Memory
824543		Amylopectin	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	876 ms	48884 KiB

Main

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int mxn = 1e6 + 10;
int n,le[40][mxn] = {},ri[40][mxn] = {},rel,rer,ldo[mxn] = {},rdo[mxn] = {};
int bui(int cl,int cr,int no,int v)
{
    if(cl == cr)
    {
        // le[][no] = cl;
        // ri[][no] = cl;
        le[v][no] = -1;
        ri[v][no] = -1;
        return 0;
    }
    int mid = (cl+cr) / 2;
    bui(cl,mid,no*2,v);
    bui(mid+1,cr,no*2+1,v);
    le[v][no] = -1;
    ri[v][no] = -1;
    // le[][no] = min(le[][no*2],le[][no*2+1]);
    // ri[][no] = max(ri[][no*2],ri[][no*2+1]);
    return 0;
}
int ad(int cl,int cr,int no,int tl,int tr,int ava,int v)
{

    if(cl > tr || cr < tl)
    {
        return 0;
    }
    if(cl >= tl && cr <= tr)
    {
        if(le[v][no] == -1)
        {
            le[v][no] = ava;
        }
        else 
        {
            le[v][no] = min(le[v][no],ava);
        }
        if(ri[v][no] == -1)
        {
            ri[v][no] = ava;
        }
        else 
        {
            ri[v][no] = max(ri[v][no],ava);
        }
        return 0;
    }
    int mid = (cl+cr) / 2;
    ad(cl,mid,no*2,tl,tr,ava,v);
    ad(mid+1,cr,no*2+1,tl,tr,ava,v);
    // le[][no] = min(le[][no*2],le[][no*2+1]);
    // ri[][no] = max(ri[][no*2],ri[][no*2+1]);
    return 0;
}
int bui2(int cl,int cr,int no,int ldow,int rdow,int v)
{
    if(le[v][no] != -1)
    {
        if(ldow != -1)
        {
            ldow = min(ldow,le[v][no]);
        }
        else 
        {
            ldow = le[v][no];
        }
    }
    if(ri[v][no] != -1)
    {
        if(rdow != -1)
        {
            rdow = max(rdow,ri[v][no]);
        }
        else 
        {
            rdow = ri[v][no];
        }
    }
    if(cl == cr)
    {
        le[v][no] = ldow;
        ri[v][no] = rdow;
        return 0;
    }
    int mid = (cl+cr) / 2;
    bui2(cl,mid,no*2,ldow,rdow,v);
    bui2(mid+1,cr,no*2+1,ldow,rdow,v);
    if(le[v][no*2] == -1)
    {
        le[v][no] = le[v][no*2 +1];
    }
    else if(le[v][no*2+1] == -1)
    {
        le[v][no] = le[v][no*2];
    }
    else 
    {
        le[v][no] = min(le[v][no*2],le[v][no*2+1]);
    }
    if(ri[v][no*2] == -1)
    {
        ri[v][no] = ri[v][no*2 +1];
    }
    else if(ri[v][no*2+1] == -1)
    {
        ri[v][no] = ri[v][no*2];
    }
    else 
    {
        ri[v][no] = max(ri[v][no*2],ri[v][no*2+1]);
    }
    
    return 0;
}
int fii(int cl,int cr,int no,int tl,int tr,int v)
{
    if(cl > tr || cr < tl)
    {
        return 0;
    }
    if(cl >= tl && cr <= tr)
    {
        if(le[v][no] != -1)
            rel = min(le[v][no],rel);
        if(ri[v][no] != -1)
            rer = max(ri[v][no],rer);
        return 0;
    }
    int mid = (cl+cr) / 2;
    fii(cl,mid,no*2,tl,tr,v);
    fii(mid+1,cr,no*2+1,tl,tr,v);
    return 0;
}
int bui3(int cl,int cr,int no,int v)
{
    if(cl == cr)
    {
        if(le[v][no] != -1)
        {
            le[v][no] = min(le[v][no],cl);
        }
        if(ri[v][no] != -1)
        {
            ri[v][no] = max(ri[v][no],cl);
        }
        rel = le[v][no];
        rer = ri[v][no];
        fii(1,n,1,le[v][no],ri[v][no],v);
        le[v+1][no] = rel;
        ri[v+1][no] = rer;
        return 0;
    }
    int mid = (cl+cr) / 2;
    bui3(cl,mid,no*2,v);
    bui3(mid+1,cr,no*2+1,v);
    if(le[v+1][no*2] == -1)
    {
        le[v+1][no] = le[v+1][no*2 +1];
    }
    else if(le[v+1][no*2+1] == -1)
    {
        le[v+1][no] = le[v+1][no*2];
    }
    else 
    {
        le[v+1][no] = min(le[v+1][no*2],le[v+1][no*2+1]);
    }
    if(ri[v+1][no*2] == -1)
    {
        ri[v+1][no] = ri[v+1][no*2 +1];
    }
    else if(ri[v+1][no*2+1] == -1)
    {
        ri[v+1][no] = ri[v+1][no*2];
    }
    else 
    {
        ri[v+1][no] = max(ri[v+1][no*2],ri[v+1][no*2+1]);
    }
    return 0;
}

int main()
{
    int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
    scanf("%d %d %d",&n,&ex,&m);
    for(i=0; i<21; i++)
    {
        bui(1,n,1,i);
    }
    for(i=0; i<m; i++)
    {
        scanf("%d %d",&cn,&cm);
        if(cn < cm)
        {
            ad(1,n,1,cn,min(cn+ex-1,cm),cm,0);
        }
        else 
        {
            ad(1,n,1,max(cn-ex+1,cm),cn,cm,0);
        }
    }
    bui2(1,n,1,-1,-1,0);
    for(i=0; i<21; i++)
    {
        bui3(1,n,1,i);
    }
    scanf("%d",&q);
    for(i=0; i<q; i++)
    {
        scanf("%d %d",&cn,&cm);
        cl = cn;
        cr = cn;
        of = 0;
        cou = 0;
        for(j=20; j>=0; j--)
        {
            rel = cl;
            rer = cr;
            fii(1,n,1,cl,cr,j);
            if(!(rel <= cm && cm <= rer))
            {
                cou += (1<<j);
                cl = rel;
                cr = rer;
            }
        }
        cou ++;
        if(cou > m)
        {
            printf("-1\n");
        }
        else 
        {
            printf("%d\n",cou);
        }
        
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:191:13: warning: unused variable 'k' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |             ^
Main.cpp:191:25: warning: unused variable 'fn' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                         ^~
Main.cpp:191:28: warning: unused variable 'fm' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                            ^~
Main.cpp:191:44: warning: unused variable 'clp' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                                            ^~~
Main.cpp:191:48: warning: unused variable 'crp' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                                                ^~~
Main.cpp:191:52: warning: variable 'of' set but not used [-Wunused-but-set-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                                                    ^~
Main.cpp:191:55: warning: unused variable 'fl' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                                                       ^~
Main.cpp:191:58: warning: unused variable 'fr' [-Wunused-variable]
  191 |     int i,j,k,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of,fl,fr;
      |                                                          ^~
Main.cpp:192:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |     scanf("%d %d %d",&n,&ex,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:199:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:214:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  214 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
Main.cpp:217:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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