Submission #824495

#	Time	Username	Problem	Language	Result	Execution time	Memory
824495		Amylopectin	Railway Trip 2 (JOI22_ho_t4)	C++14	27 / 100	2079 ms	4404 KiB

Main

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

const int mxn = 1e6 + 10;
int le[mxn] = {},ri[mxn] = {},rel,rer,ldo[mxn] = {},rdo[mxn] = {};
int bui(int cl,int cr,int no)
{
    if(cl == cr)
    {
        // le[no] = cl;
        // ri[no] = cl;
        le[no] = -1;
        ri[no] = -1;
        return 0;
    }
    int mid = (cl+cr) / 2;
    bui(cl,mid,no*2);
    bui(mid+1,cr,no*2+1);
    le[no] = -1;
    ri[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)
{

    if(cl > tr || cr < tl)
    {
        return 0;
    }
    if(cl >= tl && cr <= tr)
    {
        if(le[no] == -1)
        {
            le[no] = ava;
        }
        else 
        {
            le[no] = min(le[no],ava);
        }
        if(ri[no] == -1)
        {
            ri[no] = ava;
        }
        else 
        {
            ri[no] = max(ri[no],ava);
        }
        return 0;
    }
    int mid = (cl+cr) / 2;
    ad(cl,mid,no*2,tl,tr,ava);
    ad(mid+1,cr,no*2+1,tl,tr,ava);
    // 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)
{
    if(le[no] != -1)
    {
        if(ldow != -1)
        {
            ldow = min(ldow,le[no]);
        }
        else 
        {
            ldow = le[no];
        }
    }
    if(ri[no] != -1)
    {
        if(rdow != -1)
        {
            rdow = max(rdow,ri[no]);
        }
        else 
        {
            rdow = ri[no];
        }
    }
    if(cl == cr)
    {
        le[no] = ldow;
        ri[no] = rdow;
        return 0;
    }
    int mid = (cl+cr) / 2;
    bui2(cl,mid,no*2,ldow,rdow);
    bui2(mid+1,cr,no*2+1,ldow,rdow);
    if(le[no*2] == -1)
    {
        le[no] = le[no*2 +1];
    }
    else if(le[no*2+1] == -1)
    {
        le[no] = le[no*2];
    }
    else 
    {
        le[no] = min(le[no*2],le[no*2+1]);
    }
    if(ri[no*2] == -1)
    {
        ri[no] = ri[no*2 +1];
    }
    else if(ri[no*2+1] == -1)
    {
        ri[no] = ri[no*2];
    }
    else 
    {
        ri[no] = max(ri[no*2],ri[no*2+1]);
    }
    
    return 0;
}
int fii(int cl,int cr,int no,int tl,int tr)
{
    if(cl > tr || cr < tl)
    {
        return 0;
    }
    if(cl >= tl && cr <= tr)
    {
        if(le[no] != -1)
            rel = min(le[no],rel);
        if(ri[no] != -1)
            rer = max(ri[no],rer);
        return 0;
    }
    int mid = (cl+cr) / 2;
    fii(cl,mid,no*2,tl,tr);
    fii(mid+1,cr,no*2+1,tl,tr);
    return 0;
}
int main()
{
    int i,j,k,n,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of;
    scanf("%d %d %d",&n,&ex,&m);
    bui(1,n,1);
    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);
        }
        else 
        {
            ad(1,n,1,max(cn-ex+1,cm),cn,cm);
        }
    }
    bui2(1,n,1,-1,-1);
    scanf("%d",&q);
    for(i=0; i<q; i++)
    {
        scanf("%d %d",&cn,&cm);
        cl = cn;
        cr = cn;
        of = 0;
        cou = 0;
        while(1)
        {
            rel = cl;
            rer = cr;
            fii(1,n,1,cl,cr);
            cou ++;
            if(rel <= cm && cm <= rer)
            {
                of = 1;
                break;
            }
            if(rel == cl && rer == cr)
            {
                of = 0;
                break;
            }
            cl = rel;
            cr = rer;
        }
        if(of == 0)
        {
            printf("-1\n");
        }
        else 
        {
            printf("%d\n",cou);
        }
        
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:142:11: warning: unused variable 'j' [-Wunused-variable]
  142 |     int i,j,k,n,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of;
      |           ^
Main.cpp:142:13: warning: unused variable 'k' [-Wunused-variable]
  142 |     int i,j,k,n,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of;
      |             ^
Main.cpp:142:27: warning: unused variable 'fn' [-Wunused-variable]
  142 |     int i,j,k,n,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of;
      |                           ^~
Main.cpp:142:30: warning: unused variable 'fm' [-Wunused-variable]
  142 |     int i,j,k,n,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of;
      |                              ^~
Main.cpp:142:46: warning: unused variable 'clp' [-Wunused-variable]
  142 |     int i,j,k,n,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of;
      |                                              ^~~
Main.cpp:142:50: warning: unused variable 'crp' [-Wunused-variable]
  142 |     int i,j,k,n,m,q,cn,cm,fn,fm,ex,cou,cl,cr,clp,crp,of;
      |                                                  ^~~
Main.cpp:143:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |     scanf("%d %d %d",&n,&ex,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:158:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
Main.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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