2021.12.21 eleveni的刷题记录
2021.12.21 eleveni的刷题记录
0. 有意思的题
P6701 [POI1997] Genotype
https://www.luogu.com.cn/problem/P6701
状压优化区间DP
P1712 [NOI2016] 区间
https://www.luogu.com.cn/problem/P1712
线段树+尺取法
1. 动态规划
1.1 二进制优化
https://www.luogu.com.cn/problem/P1776
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=3e5+10;
int n,W,top,f[N];
struct node{
int val,cost;
}a[N];
int main(){
IOS;
cin>>n>>W;
for(int i=1;i<=n;i++){
int val,cost,num;
cin>>val>>cost>>num;
for(int j=1;j<=num;j*=2){
++top;
a[top].val=val*j;a[top].cost=cost*j;
num-=j;
}
if(num)++top,a[top].val=val*num,a[top].cost=cost*num;
}
//for(int i=1;i<=top;i++)cout<=a[i].cost;j--)
f[j]=max(f[j],f[j-a[i].cost]+a[i].val);
//for(int i=1;i<=W;i++)cout< 1.2 01背包
https://www.luogu.com.cn/problem/P1855
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=210;
int n,M,T,f[N][N];
struct node{
int m,t;
}a[N];
int main(){
IOS;
cin>>n>>M>>T;
for(int i=1;i<=n;i++)cin>>a[i].m>>a[i].t;
for(int i=1;i<=n;i++)
for(int j=M;j>=a[i].m;j--)
for(int k=T;k>=a[i].t;k--)
f[j][k]=max(f[j][k],f[j-a[i].m][k-a[i].t]+1);
cout< 1.3 区间DP
luogu.com.cn/problem/P4342
#include
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
const int N=110;
const int inf=0x3f3f3f3f;
int n,num[N],flag[N],f[N][N],g[N][N];
dequeq;
signed main(){
cin>>n;
for(int i=1;i<=n*2;i++)for(int j=1;j<=n*2;j++)f[i][j]=-inf,g[i][j]=inf;
for(int i=1;i<=n;i++){
char ch;cin>>ch;
int x=i-1?i-1:n;
flag[x]=flag[x+n]=ch=='t'?-1:1;
cin>>num[i];
g[i+n][i+n]=f[i+n][i+n]=g[i][i]=f[i][i]=num[i+n]=num[i];
}
//for(int i=1;i<=n*2;i++)cout<maxn)maxn=f[i][i+n-1];
cout< https://www.luogu.com.cn/problem/P5851
#include
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=310;
int n,m,f[N][N],g[N][N][N];
int main(){
IOS;
cin>>n>>m;
for(int i=1;i<=m;i++){
int w,l,r;
cin>>w>>l>>r;
for(int j=l;j<=r;j++)g[j][l][r]=max(g[j][l][r],w);
}
for(int k=1;k<=n;k++)
for(int i=k;i>=1;i--)for(int j=k;j<=n;j++){
if(i!=1)g[k][i-1][j]=max(g[k][i-1][j],g[k][i][j]);
if(j!=n)g[k][i][j+1]=max(g[k][i][j+1],g[k][i][j]);
}
for(int i=n;i>=1;i--)for(int j=i;j<=n;j++){
for(int k=i;k 1.3.1 状态压缩优化区间DP
https://www.luogu.com.cn/problem/P6701
为毛空间开大了会TLE？？？？？行吧，我估计是memset的大锅！
#include
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=310;
const int inf=0x3f3f3f3f;
int n,m,mapi[30][30],f[N][N],num[N][N],tmp[N];
inline void solve(string s){
memset(f,inf,sizeof(f));
memset(num,0,sizeof(num));
int len=s.length();
for(int i=1;i<=len;i++){
num[i][i]|=1<<(s[i-1]-'A'+1);
if(s[i-1]=='S')f[i][i]=1;
}
for(int l=2;l<=len;l++)
for(int i=1;i+l-1<=len;i++){
int j=i+l-1;
for(int k=i;k=inf)cout<<"NIE"<>n;
for(int i=1;i<=n;i++){
string s;cin>>s;
mapi[s[1]-'A'+1][s[2]-'A'+1]|=1<<(s[0]-'A'+1);
}
cin>>m;
for(int i=1;i<=m;i++){
string s;cin>>s;
solve(s);
}
return 0;
}
1.3.2 区间DP重要思路1（这题里面蕴含的思想就是把答案放进 dp 数组的某一维中。
为什么要这样做？因为答案的值域远小于 T 的值域。）
https://www.luogu.com.cn/problem/P1220
类似于P1220关路灯
温馨提示： 题面错误，从起点出发！！！
这题里面蕴含的思想就是把答案放进 dp 数组的某一维中。
为什么要这样做？因为答案的值域远小于 T 的值域。
0pts：
#include
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=410;
const int inf=0x3f3f3f3f;
int n,L,f[N][N][2],num[N][N][2];
struct node{
int pos,time;
bool operator <(const node &b)const{
return pos>n>>L;
for(int i=1;i<=n;i++)cin>>a[i].pos,a[i+n].pos=a[i].pos+L;
for(int i=1;i<=n;i++)cin>>a[i].time,a[i+n].time=a[i].time;
memset(f,inf,sizeof(f));
for(int i=1;i<=n*2;i++)num[i][i][0]=num[i][i][1]=1,f[i][i][0]=f[i][i][1]=0;
sort(a+1,a+n*2+1);
for(int len=2;len<=n;len++)
for(int i=1;i+len-1<=n*2;i++){
int j=i+len-1;
int x=f[i+1][j][0]+a[i+1].pos-a[i].pos,y=f[i+1][j][1]+a[j].pos-a[i].pos;
if(x<=a[i].time&&y<=a[i].time)
f[i][j][0]=min(x,y),num[i][j][0]=max(num[i+1][j][0],num[i+1][j][1])+1;
else if(x<=a[i].time)
f[i][j][0]=x,num[i][j][0]=num[i+1][j][0]+1;
else if(y<=a[i].time)
f[i][j][0]=y,num[i][j][0]=num[i+1][j][1]+1;
else if(xy)f[i][j][0]=y,num[i][j][0]=num[i+1][j][1];
else f[i][j][0]=x,num[i][j][0]=max(num[i+1][j][0],num[i+1][j][1]);
x=f[i][j-1][0]+a[j].pos-a[i].pos,y=f[i][j-1][1]+a[j].pos-a[j-1].pos;
if(x<=a[j].time&&y<=a[j].time)
f[i][j][1]=min(x,y),num[i][j][1]=max(num[i][j-1][0],num[i][j-1][1])+1;
else if(x<=a[j].time)
f[i][j][1]=x,num[i][j][1]=num[i][j-1][0]+1;
else if(y<=a[j].time)
f[i][j][1]=y,num[i][j][1]=num[i][j-1][1]+1;
else if(xy)f[i][j][1]=y,num[i][j][1]=num[i][j-1][1];
else f[i][j][1]=x,num[i][j][1]=max(num[i][j-1][0],num[i][j-1][1]);
}
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,max(num[i][i+n-1][0],num[i][i+n-1][1]));
cout< 100pts：
#include
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=210;
const int inf=0x3f3f3f3f;
int n,len,f[N][N][N][2],num[N][N][2];
struct node{
int pos,time;
bool operator <(const node &b)const{
return pos>n>>len;
for(int i=1;i<=n;i++)cin>>a[i].pos;
for(int i=1;i<=n;i++)cin>>a[i].time;
memset(f,inf,sizeof(f));
a[n+1].pos=len;
f[0][0][0][0]=f[0][0][0][1]=0;
for(int L=0;L<=n;L++)
for(int R=0;R+L<=n;R++)
for(int k=0;k<=R+L;k++){
int now=f[L][R][k][0];
if(now<=inf){
int add=now+a[n-L+1].pos-a[n-L].pos;
f[L+1][R][k+(add<=a[n-L].time)][0]=min(f[L+1][R][k+(add<=a[n-L].time)][0],add);
add=now+len-a[n-L+1].pos+a[R+1].pos;
f[L][R+1][k+(add<=a[R+1].time)][1]=min(f[L][R+1][k+(add<=a[R+1].time)][1],add);
}
now=f[L][R][k][1];
if(now<=inf){
int add=now+len-a[n-L].pos+a[R].pos;
f[L+1][R][k+(add<=a[n-L].time)][0]=min(f[L+1][R][k+(add<=a[n-L].time)][0],add);
add=now+a[R+1].pos-a[R].pos;
f[L][R+1][k+(add<=a[R+1].time)][1]=min(f[L][R+1][k+(add<=a[R+1].time)][1],add);
}
}
int ans=0;
for(int L=0;L<=n;L++)
for(int R=0;R+L<=n;R++)
for(int k=0;k<=R+L;k++)
if(min(f[L][R][k][0],f[L][R][k][1]) 1.3.3 组合数学+区间DP
https://www.luogu.com.cn/problem/P2523
IOS关了的同时不能用puts！
#include
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
const int N=310;
int T,n,m,mod,f[N][N],C[N][N],sum[N];
signed main(){
IOS;
cin>>T;
while(T--){
cin>>n>>m>>mod;
memset(sum,0,sizeof(sum));
memset(f,0,sizeof(f));
memset(C,0,sizeof(C));
for(int i=0;i<=300;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j>x>>y;
++sum[y];
}
for(int i=n;i>=1;i--)sum[i]+=sum[i+1];
for(int i=1;i<=n;i++)if(sum[i]>n-i+1){
cout<<"NO"<0)f[n+1][i]=0;else f[n+1][i]=1;
for(int i=n;i>=1;i--)
for(int j=0;j<=n-i+1-sum[i];++j)
for(int k=0;k<=j;k++)
f[i][j]=(f[i][j]+C[j][k]*f[i+1][j-k]%mod)%mod;
cout<<"YES "< 1.4 树形DP
https://www.luogu.com.cn/problem/P4516
卡long long的脑残题！
#include
#include
#include
#include
#define ls (x)<<1
#define rs (x)<<1|1
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e5+10;
int n,m,f[N][110][2][2],tmp[110][2][2],sizei[N];
int cnt,head[N];
struct node{
int to,next;
}a[N*2];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
++cnt;
a[cnt].to=v;
a[cnt].next=head[u];
head[u]=cnt;
}
inline int plusi(int x,long long y){
//while(y>=mod)y-=mod;
//while(x>=mod)x-=mod;
y+=x;
while(y>=mod)y-=mod;
return y;
}
inline void dfs(int x,int fa){
sizei[x]=f[x][0][0][0]=f[x][1][1][0]=1;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fa)continue;
dfs(v,x);
for(int j=0;j<=min(sizei[x],m);j++){
tmp[j][0][0]=f[x][j][0][0]%mod;f[x][j][0][0]=0;
tmp[j][0][1]=f[x][j][0][1]%mod;f[x][j][0][1]=0;
tmp[j][1][0]=f[x][j][1][0]%mod;f[x][j][1][0]=0;
tmp[j][1][1]=f[x][j][1][1]%mod;f[x][j][1][1]=0;
}
for(int j=0;j<=min(sizei[x],m);j++)
for(int k=0;k<=min(m-j,sizei[v]);k++){
f[x][j+k][0][0]=plusi(f[x][j+k][0][0],
1ll*f[v][k][0][1]*tmp[j][0][0]%mod)%mod;
f[x][j+k][1][0]=plusi(f[x][j+k][1][0],
plusi(f[v][k][0][1],f[v][k][0][0])%mod*1ll*tmp[j][1][0]%mod)%mod;
f[x][j+k][0][1]=plusi(f[x][j+k][0][1],
1ll*f[v][k][1][1]*tmp[j][0][0]%mod)%mod;
f[x][j+k][0][1]=plusi(f[x][j+k][0][1],
plusi(f[v][k][0][1],f[v][k][1][1])%mod*1ll*tmp[j][0][1]%mod)%mod;
f[x][j+k][1][1]=plusi(f[x][j+k][1][1],
plusi(f[v][k][1][0],f[v][k][1][1])%mod*1ll*tmp[j][1][0]%mod)%mod;
f[x][j+k][1][1]=plusi(f[x][j+k][1][1],
plusi(f[v][k][0][0],plusi(f[v][k][0][1],plusi(f[v][k][1][0],f[v][k][1][1])))%mod*1ll*tmp[j][1][1]%mod)%mod;
}
sizei[x]+=sizei[v];
}
}
int main(){
n=read();m=read();
for(int i=1;i 1.4.1 贪心+树形DP
https://www.luogu.com.cn/problem/P3574
一般来说如果和子节点有关可以先把子节点记录下来进行排序，再进行操作
#include
#include
#include
#include
#define ls (x)<<1
#define rs (x)<<1|1
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
const int N=5e5+10;
int n,val[N],f[N],son[N],tmp[N];
int cnt,head[N];
struct node{
int to,next;
}a[N*2];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
++cnt;
a[cnt].to=v;
a[cnt].next=head[u];
head[u]=cnt;
}
inline int cmp(int x,int y){
return son[x]-f[x] 1.4.2 换根DP
树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。
通常需要两次 DFS，第一次 DFS 预处理诸如深度，点权和之类的信息，在第二次 DFS 开始运行换根动态规划。
https://www.luogu.com.cn/problem/P2986
#include
#include
#include
#include
#define ls (x)<<1
#define rs (x)<<1|1
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
const int N=1e5+10;
int n,ans=1e18,f[N],len[N],num[N],sizei[N];
int cnt,head[N];
struct node{
int to,next,val;
}a[N*2];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void add(int u,int v,int w){
++cnt;
a[cnt].to=v;
a[cnt].val=w;
a[cnt].next=head[u];
head[u]=cnt;
}
inline void dfs(int x,int fa){
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fa)continue;
dfs(v,x);
len[x]+=len[v]+sizei[v]*a[i].val;
sizei[x]+=sizei[v];
}
}
inline void dfs_dp(int x,int fa){
ans=min(ans,f[x]);
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fa)continue;
f[v]=f[x]+(sizei[1]-sizei[v])*a[i].val-sizei[v]*a[i].val;
dfs_dp(v,x);
}
}
signed main(){
n=read();
for(int i=1;i<=n;i++)sizei[i]=read();
for(int i=1;i https://www.luogu.com.cn/problem/CF708C
难得……心塞
#include
#include
#include
#include
#define ls (x)<<1
#define rs (x)<<1|1
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=4e5+10;
int n,sizei[N],maxn[N][2],f[N],g[N],fin[N];
int cnt,head[N];
struct node{
int to,next;
}a[N*2];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
++cnt;
a[cnt].to=v;
a[cnt].next=head[u];
head[u]=cnt;
}
inline void dfs1(int x,int fa){
sizei[x]=1;f[x]=g[x]=0;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fa)continue;
dfs1(v,x);
sizei[x]+=sizei[v];
g[x]=max(g[x],g[v]);
if(sizei[v]>sizei[maxn[x][0]])maxn[x][1]=maxn[x][0],maxn[x][0]=v;
else if(sizei[v]>sizei[maxn[x][1]])maxn[x][1]=v;
}
if(sizei[x]<=n/2)g[x]=sizei[x];
}
inline void dfs2(int x,int fa){
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fa)continue;
if(n-sizei[v]<=n/2)f[v]=n-sizei[v];
else if(v!=maxn[x][0])f[v]=max(f[x],g[maxn[x][0]]);
else f[v]=max(f[x],g[maxn[x][1]]);
dfs2(v,x);
}
if(n-sizei[x]>sizei[maxn[x][0]])fin[x]=n-sizei[x]-f[x]<=n/2;
else fin[x]=sizei[maxn[x][0]]-g[maxn[x][0]]<=n/2;
}
signed main(){
n=read();
for(int i=1;i https://www.luogu.com.cn/problem/P3047
#include
#include
#include
#include
#define ls (x)<<1
#define rs (x)<<1|1
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1e5+10;
int n,m,f[N][25],ans[N],val[N];
int cnt,head[N];
struct node{
int to,next;
}a[N*2];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
++cnt;
a[cnt].to=v;
a[cnt].next=head[u];
head[u]=cnt;
}
inline void dfs1(int x,int fa){
f[x][0]=val[x];
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fa)continue;
dfs1(v,x);
for(int j=1;j<=m;j++)f[x][j]+=f[v][j-1];
}
}
inline void pre(int x,int y){
for(int i=1;i<=m;i++)f[x][i]-=f[y][i-1];
}
inline void suf(int x,int y){
for(int i=1;i<=m;i++)f[x][i]+=f[y][i-1];
}
inline void change(int x,int y){
pre(x,y);
suf(y,x);
}
inline void dfs2(int x,int fa){
for(int i=0;i<=m;i++)ans[x]+=f[x][i];
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fa)continue;
change(x,v);
dfs2(v,x);
change(v,x);
}
}
int main(){
n=read();m=read();
for(int i=1;i 1.5 状压DP
https://www.luogu.com.cn/problem/UVA10817
出现 No valid executable file was produced by the compiler 可能是空间炸了……离谱……
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=130;
const int M=1<<9;
const int inf=0x3f3f3f3f;
int S,n,m,f[N][M][M],val[N],ans,teach[N];
inline void change1(string s,int &num1,int &num2){
int num=0;
for(int i=0;i<(int)s.length();i++)
if(s[i]>='0'&&s[i]<='9')num=num*10+s[i]-'0';
else if(num){
if(!(num2&(1<>val[i];ans+=val[i];
//cout<<"i "<>val[i];
string s;getline(cin,s);
s=s+'*';
int x=0;
change1(s,x,x);
teach[i]=x;
//cout< 2.图论
2.1 网络流
2.1.1 费用流EK
https://www.luogu.com.cn/problem/P4016
#include
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=210;
const int inf=0x3f3f3f3f;
int n,num[N],aver,start,endi,maxnflow,maxncost,cnt=1,head[N],dis[N],vis[N],flow[N],pre[N];
struct node{
int to,next,val,cost;
}a[N*10];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void addi(int u,int v,int w,int x){
++cnt;
a[cnt].to=v;
a[cnt].val=w;
a[cnt].cost=x;
a[cnt].next=head[u];
head[u]=cnt;
}
inline void add(int u,int v,int w,int x){
addi(u,v,w,x);addi(v,u,0,-x);
}
inline int spfa(int s,int t){
memset(dis,inf,sizeof(dis));
memset(vis,0,sizeof(vis));
queueq;
dis[s]=0;flow[s]=inf;vis[s]=1;
q.push(s);
while(!q.empty()){
int x=q.front();q.pop();
vis[x]=0;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(dis[v]>dis[x]+a[i].cost&&a[i].val>0){
dis[v]=dis[x]+a[i].cost;
flow[v]=min(flow[x],a[i].val);
pre[v]=i;
if(!vis[v]&&a[i].val)vis[v]=1,q.push(v);
}
}
}
return dis[t]!=inf;
}
inline void update(int s,int t){
int x=t;
while(x!=s){
int xi=pre[x];
a[xi].val-=flow[t];
a[xi^1].val+=flow[t];
x=a[xi^1].to;
}
maxnflow+=flow[t];
maxncost+=flow[t]*dis[t];
}
inline void EK(int s,int t){
while(spfa(s,t))update(s,t);
}
int main(){
n=read();
start=n+1,endi=n+2;
for(int i=1;i<=n;i++)num[i]=read(),aver+=num[i];
aver/=n;
for(int i=1;i<=n;i++){
int x=num[i]-aver;
//cout<0)add(start,i,x,0);
if(x<0)add(i,endi,-x,0);
add(i,i+1>n?1:i+1,inf,1),add(i,i-1<1?n:i-1,inf,1);
}
//cout< 3. 数据结构
3.1 线段树
https://www.luogu.com.cn/problem/P1712
尺取法：
#include
#include
#include
#include
#define ls (x)<<1
#define rs (x)<<1|1
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1e6+10;
int n,a[N],m;
struct node{
int l,r,val,lazy;
}t[N<<4];
struct nodei{
int l,r,len;
bool operator <(const nodei &b)const{
return len'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void pushdown(int x){
if(!t[x].lazy)return ;
t[ls].lazy+=t[x].lazy;t[rs].lazy+=t[x].lazy;
t[ls].val+=t[x].lazy;t[rs].val+=t[x].lazy;
t[x].lazy=0;
}
inline void build(int x,int l,int r){
t[x].l=l;t[x].r=r;t[x].val=t[x].lazy=0;
if(l==r)return ;
int mid=(l+r)>>1;
build(ls,l,mid);build(rs,mid+1,r);
t[x].val=max(t[ls].val,t[rs].val);
}
inline void change(int x,int l,int r,int L,int R,int k){
if(l>R||r=L&&r<=R)return (void)(t[x].val+=k,t[x].lazy+=k);
pushdown(x);
int mid=(l+r)>>1;
if(L<=mid)change(ls,l,mid,L,R,k);
if(R>mid)change(rs,mid+1,r,L,R,k);
t[x].val=max(t[ls].val,t[rs].val);
}
inline int query(int x,int l,int r,int L,int R){
if(l>R||r=L&&r<=R)return t[x].val;
pushdown(x);
int mid=(l+r)>>1;
int ans=0;
if(L<=mid)ans=max(ans,query(ls,l,mid,L,R));
if(R>mid)ans=max(ans,query(rs,mid+1,r,L,R));
t[x].val=max(t[ls].val,t[rs].val);
return ans;
}
signed main(){
n=read();m=read();
for(int i=1;i<=n;i++){
q[i].l=read();q[i].r=read();
q[i].len=q[i].r-q[i].l;
a[i*2-1]=q[i].l;a[i*2]=q[i].r;
}
sort(a+1,a+n*2+1);
sort(q+1,q+n+1);
int len=unique(a+1,a+n*2+1)-a-1;
build(1,1,len);
int ans=0x3f3f3f3f,aim=1;
//cout<=m){
ans=min(ans,q[i].len-q[aim].len);
L=lower_bound(a+1,a+len+1,q[aim].l)-a;
R=lower_bound(a+1,a+len+1,q[aim].r)-a;
change(1,1,len,L,R,-1);
++aim;
}
}
if(ans==0x3f3f3f3f)cout<<"-1";
else cout<