subject

Portal to CF

thinking

The point is to find out what the operation of the tank should be.

For example, we can easily find that if you destroy an obstacle, you should drive over its ruins. However, what is more important and more difficult to find is that you should not change lanes before walking to the ruins.

Why? Suppose you change your way out and then come back (to run over the ruins), because the shell will not be blocked in this section (can hit the ruins behind), so you don't bypass the obstacles; The only possibility is that you used to fire. According to the "must run over ruins" theory, you need to run over all new ruins.

If the new ruins were in front of the original ruins, wouldn't it ask for trouble - why not bypass it and go straight to the original road? After all, you will eventually reach the original ruins. If you go the same way, you can shoot less. It must be better.

So the new ruins are behind the original ruins (or the same column). But this is absurd. Where shells can reach, tanks can reach. So the tank can go another way, go around the original ruins, and then reach the new ruins. After all, you will eventually reach the new ruins. The two are equivalent. So, at first, tanks didn't need to bombard the original ruins at all!

Finish the certificate. At this time, we will find that when the tank has just come to a road, the obstacles in front of it should not have been bombarded. So there is no need to store the status of obstacles! Just consider the process of starting from a certain place and going back!

Take advantage of the ability to fire in advance. Let's go x x Step x can be opened ⌊ x t ⌋ \lfloor{x\over t}\rfloor ⌊ tx ⌋ gun. In fact, it is equivalent to the consumption of each shot t t t's energy, and then move to accumulate energy all the time. Design d p \tt dp dp is f ( x , y ) f(x,y) f(x,y) represents walking to ( x , y ) (x,y) How much energy can there be at (x,y). The transfer is clearly from f ( x , y ⊕ 1 ) f(x,y\oplus 1) f(x,y ⊕ 1) and f ( x − 1 , y ) f(x{\rm-}1,y) f(x − 1,y) is transferred.

Changing lanes at any place between the nearest obstacles has the same effect. You might as well let them change lanes immediately after passing an obstacle. here x x The value of x is only O ( m 1 + m 2 ) \mathcal O(m_1+m_2) O(m1 + m2), you can pass this question.

code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MAXN = 1000005;
int x[2][MAXN], m[2], all[MAXN<<1], t;
int dp[MAXN<<1][2], pre[MAXN<<1][2];

int lc[MAXN], cnt_lc; // lane changing
int shot[MAXN][2], cnt_shot;
/// @return last position to shot
int print(int r,int y){
	if(!r && !y) return 0; // just began cooling time
	if(pre[r][y] == 1){
		print(r,y^1), lc[++ cnt_lc] = all[r];
		return all[r]-dp[r][y]; // what's saved
	}
	if(pre[r][y] == 0) return print(r-1,y);
	int lst = print(r-1,y)+t; // one more shot
	shot[++ cnt_shot][0] = lst;
	return shot[cnt_shot][1] = y+1, lst;
}
int main(){
	scanf("%*d"); // n is useless
	rep(i,0,1) m[i] = readint();
	t = readint();
	rep(d,0,1) rep(i,1,m[d]) x[d][i] = readint();
	for(int a=1,b=1; a<=m[0]||b<=m[1]; )
		if(b > m[1] || (a <= m[0] && x[0][a] <= x[1][b]))
			all[a+b-1] = x[0][a], ++ a;
		else all[a+b-1] = x[1][b], ++ b; // merge sort
	int tot = unique(all+1,all+m[0]+m[1]+1)-all-1;
	drep(i,tot,1) all[i<<1] = all[i]+1, all[(i<<1)-1] = all[i];
	tot = unique(all+1,all+(tot<<1)+1)-all-1;
	all[0] = 0, dp[0][0] = dp[0][1] = 0;
	pre[0][1] = 1; // from lane changing
	for(int i=1,now[2]={1,1}; i<=tot; ++i){
		for(int d=0; d!=2; ++d){
			while(now[d] <= m[d] && x[d][now[d]] < all[i]) ++ now[d];
			dp[i][d] = dp[i-1][d]+(all[i]-all[i-1]); // charged
			if(dp[i-1][d] == -1) dp[i][d] = -1; // cannot transfer
			if(x[d][now[d]] == all[i]){
				dp[i][d] -= t; // make shot lose energy
				if(dp[i][d] > 0) pre[i][d] = 2; // shot
				else dp[i][d] = -1; // fail to do that
			}
			else pre[i][d] = 0; // just move ahead
		}
		rep(d,0,1) if(dp[i][d^1] >= 0 && x[d][now[d]] != all[i])
			if(dp[i][d] < min(dp[i][d^1],t)) // at most one shot
				dp[i][d] = min(dp[i][d^1],t), pre[i][d] = 1; // change lane
	}
	if(dp[tot][0] >= 0 || dp[tot][1] >= 0){
		puts("Yes"), print(tot,bool(dp[tot][1]>=0));
		printf("%d\n",cnt_lc);
		rep(i,1,cnt_lc) printf("%d ",lc[i]);
		printf("\n%d\n",cnt_shot);
		rep(i,1,cnt_shot) printf("%d %d\n",shot[i][0],shot[i][1]);
		putchar('\n');
	}
	else puts("No");
	return 0;
}