# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
824543 | Amylopectin | Railway Trip 2 (JOI22_ho_t4) | C++14 | 876 ms | 48884 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |