Submission #5546151
Source Code Expand
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=200010;
int n,m,q,tot,tot2,cnt,tmp,ans;
int f[maxn][20];
int head[maxn];
ll aa[maxn],l;
ll dis[maxn];
int dfn[maxn],d[maxn];
int dep[maxn],e[maxn],pos[maxn];
int ok[maxn];
bool vis[maxn];
struct node
{
int to,nex;
ll w;
}a[maxn];
void add(int u,int v,ll w)
{
//cout<<u<<"->"<<v<<endl;
a[cnt].to=v;
a[cnt].w=w;
a[cnt].nex=head[u];
head[u]=cnt++;
}
void init()
{
cnt=tot=tot2=0;
for(int i=0;i<=2*n;i++)
{
head[i]=-1;pos[i]=-1;
vis[i]=0;
ok[i]=0;
}
dis[1]=0;
}
void dfs(int u,int deep)//1
{
if(pos[u]!=-1)return;
dfn[tot2]=u;d[u]=tot2++;
pos[u]=tot;e[tot]=u;dep[tot++]=deep;
for(int i=head[u];i!=-1;i=a[i].nex)
{
int v=a[i].to;
if(pos[v]==-1)
{
dis[v]=dis[u]+a[i].w;
dfs(v,deep+1);
e[tot]=u;dep[tot++]=deep;
}
}
}
void rmq(int n)//2
{
for(int i=1;i<=n;i++)f[i][0]=i;
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
{
if(dep[f[i][j-1]]<dep[f[i+(1<<(j-1))][j-1]]) f[i][j]=f[i][j-1];
else f[i][j]=f[i+(1<<(j-1))][j-1];
}
}
int RMQ(int l,int r)
{
int k=(int)(log((double)(r-l+1))/log(2.0));
if(dep[f[l][k]]<dep[f[r-(1<<k)+1][k]]) return f[l][k];
else return f[r-(1<<k)+1][k];
}
int lca(int x,int y)//3
{
if(pos[x]<pos[y]) return e[RMQ(pos[x],pos[y])];
else return e[RMQ(pos[y],pos[x])];
}
ll cal(int x,int y)
{
return dis[x]+dis[y]-2*dis[lca(x,y)];
}
int main()
{
int T,cas=1;
while(scanf("%d",&n)!=EOF)
{
init();
for(int i=1;i<=n;i++)
scanf("%lld",&aa[i]);
scanf("%lld",&l);
for(int i=1;i<=n;i++)
if(!ok[i]){
int j=i,k=i;
while(k<n)
{
while(j+1<=n&&aa[j+1]-aa[k]<=l)
{
j++;
if(ok[j])
{
ok[k]=j;
add(k,j,1LL);
add(j,k,1LL);
k=n;
break;
}
}
if(k==n) break;
if(!ok[j])
{
ok[j]=k;ok[k]=j;
add(k,j,1LL);
add(j,k,1LL);
}
k=j;
}
}
//printf("Case #%d:\n",cas++);
dfs(1,0);
rmq(2*n-1);//4
ll ans=0;
scanf("%d",&q);
while(q--)
{
int u,v;
scanf("%d %d",&u,&v);
ans=cal(u,v);
if(llabs(aa[u]-aa[v])<=l) ans=1;
printf("%lld\n",ans);
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Tak and Hotels |
User |
IGVA |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2934 Byte |
Status |
WA |
Exec Time |
3155 ms |
Memory |
33024 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:87:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&aa[i]);
^
./Main.cpp:88:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&l);
^
./Main.cpp:120:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
./Main.cpp:124:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&u,&v);
^
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
0 / 200 |
0 / 500 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
example_01.txt |
Subtask1 |
example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt |
All |
example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt |
Case Name |
Status |
Exec Time |
Memory |
example_01.txt |
AC |
7 ms |
10880 KB |
subtask1_01.txt |
WA |
3 ms |
10496 KB |
subtask1_02.txt |
AC |
3 ms |
10496 KB |
subtask1_03.txt |
WA |
4 ms |
10496 KB |
subtask1_04.txt |
AC |
4 ms |
10496 KB |
subtask1_05.txt |
WA |
4 ms |
10496 KB |
subtask1_06.txt |
AC |
3 ms |
10496 KB |
subtask1_07.txt |
WA |
3 ms |
10496 KB |
subtask1_08.txt |
AC |
4 ms |
10496 KB |
subtask1_09.txt |
WA |
4 ms |
10496 KB |
subtask1_10.txt |
WA |
4 ms |
10496 KB |
subtask1_11.txt |
WA |
4 ms |
10496 KB |
subtask1_12.txt |
WA |
4 ms |
10496 KB |
subtask1_13.txt |
WA |
4 ms |
10496 KB |
subtask2_01.txt |
WA |
77 ms |
28544 KB |
subtask2_02.txt |
AC |
80 ms |
33024 KB |
subtask2_03.txt |
WA |
86 ms |
28160 KB |
subtask2_04.txt |
AC |
2149 ms |
22912 KB |
subtask2_05.txt |
WA |
50 ms |
23296 KB |
subtask2_06.txt |
TLE |
3155 ms |
11776 KB |
subtask2_07.txt |
WA |
80 ms |
28672 KB |
subtask2_08.txt |
WA |
80 ms |
31488 KB |
subtask2_09.txt |
WA |
78 ms |
31488 KB |
subtask2_10.txt |
WA |
80 ms |
31488 KB |
subtask2_11.txt |
WA |
74 ms |
30336 KB |
subtask2_12.txt |
WA |
68 ms |
33024 KB |
subtask2_13.txt |
WA |
2518 ms |
28032 KB |