Codeforces 1236E. Alice and the Unfair Game - 1236e, alice, codeforces, game, unfair

Portal

First notice that The fixed starting point is $S$, and the end point it can eventually reach must be a range

This is easy to prove by contradiction, assuming it is legal There is a breakpoint in the interval, and this point can be used as the end point.

Then divide the interval breakpoint into the left side of the starting point and the right side of the starting point. Yes,The starting point itself can obviously be used as the ending point

Then now you can calculate the answer by considering the leftmost and rightmost positions that you can go from each starting point.

Consider first To the right (for convenience, the $i$th inquiry is referred to as the $i$th day)

set the starting point as $x $ Then we can keep going to the right until we encounter the next position we were going to ask for on a certain day, then we have to stop once

Suppose you have gone for $y$ days and encounter this situation, then $x+y=a[y]$, that is, $x=a[y]-y$, and then we will have to wait for one step Find the next $y$ such that $x+1+y=a[y]$

Set $f(x,y )$ represents the rightmost position that can be reached from $x$ on day $y$, then only $f(x,y)$ is required. The first stop position to the right then becomes the position further to the right, the number of days The bigger sub-problem

Let $z$ be the smallest one that satisfies $x+z=a[y+z]$ Number, then the conversion is equivalent to $xy=a[y+z]-(y+z)$

to The first stop position on the right is obviously It can be maintained, as long as you consider the time one by one, use a $map$ to maintain the first $a[i]-i$ query from the left after the current time

At the same time, notice that only when it happens to be at position $a[i]-1$ and time is at $i$ will stop once, then the position we want to know is It is only related to the inquiry time, so the maintenance time can be used.

Then the summary is to enumerate by time $i$ from large to small , Make a $map$ to maintain the current smallest $j>i$ so that $a[j]-j==(a[i]-1)-i$

Then you can find out that $R[i]$ means going to the right just at the time $i$ stop for one day and then continue walking to the far right end ($R[i]= R[j]$,$j=map[(a[i]-1)-i]$, which means to find the next stop time point to transfer)

Of course, if there is no legal $j$ in $map$, then it means that you don’t need to stop, just go to the end of the time

The same is true for going to the left, learn the above ideas and push it yourself

Facts The upper $map$ can be completely replaced by a bucket, just add $m$ to the subscript collectively

Code reference: Farhod_Farmon< /span>

#include

#include

#include

#include

#include

#include

using namespace std;

typedef long long ll;

inline int read()

{

 int x=0,f=1; char ch=getchar();

 while(ch<'0'||ch>' 9') {if< /span>(ch=='-') f=-1; ch=getchar();}

 while(ch>='0'&&ch<=' 9') {x=(x<<1)+(x<<3)+(ch^48 ); ch=getchar();}

 return x*f;

}

const int N=1e5+7;

int n,m,A[N],L[N] ,R[N];

map <int,int> ml,mr;

inline int find_r(int x,int i) {return mr[xi]? R[mr[xi]]: min(x+ (mi)+1,n);}

inline int find_l(int x,int i) {return ml[x+i]? L[ml[x+i]] : max(x-(mi)-1,1);}

int main()

{

 n=read(),m=read();

 for(int i=1;i<=m;i++) A[i]=read();

 if(n==1) {printf( "0
"< /span>); return 0;}

 for(int i=m;i>= 1;i--)

 {

 L[i]=find_l(A[i]+1,i); R[i]=find_r(A[ i]-1,i);

 ml[A[i]+i]=i; mr[A[i]-i]=i;

}

 ll ans=0;

 for(int i=1;i<=n;i++)

 ans+=find_r(i,0)-i+1+i-find_l(i,0);//The +1 in the middle is the starting point itself as End-point contribution

 printf("%lld
",ans);

 return 0;

}

#include

#include

#include

#include

#include

#include

using namespace std;

typedef long long ll;

inline int read()

{

 int x=0,f=1; char ch=getchar();

 while(ch<'0'||ch>' 9') {if< /span>(ch=='-') f=-1; ch=getchar();}

 while(ch>='0'&&ch<=' 9') {x=(x<<1)+(x<<3)+(ch^48 ); ch=getchar();}

 return x*f;

}

const int N=1e5+7;

int n,m,A[N],L[N] ,R[N];

map <int,int> ml,mr;

inline int find_r(int x,int i) {return mr[xi]? R[mr[xi]]: min(x+ (mi)+1,n);}

inline int find_l(int x,int i) {return ml[x+i]? L[ml[x+i]] : max(x-(mi)-1,1);}

int main()

{

 n=read(),m=read();

 for(int i=1;i<=m;i++) A[i]=read();

 if(n==1) {printf( "0
"< /span>); return 0;}

 for(int i=m;i>= 1;i--)

 {

 L[i]=find_l(A[i]+1,i); R[i]=find_r(A[ i]-1,i);

 ml[A[i]+i]=i; mr[A[i]-i]=i;

}

 ll ans=0;

 for(int i=1;i<=n;i++)

 ans+=find_r(i,0)-i+1+i-find_l(i,0);//The +1 in the middle is the starting point itself as End-point contribution

 printf("%lld
",ans);

 return 0;

}

Leave a Comment Cancel reply