nfls day 15

e

T1 & T2 & T3 挺水的我觉得
T4 单调队列？水
T5 卡了一会，cqr DALAO 直接快速A了 膜拜！
就DP那段卡了挺久
T6 直接倍增+DP A掉，不会很难
log取值注意下就行

//F-Code 
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define Sig signed
#define uSig unsigned
#define ll long long
//#define int ll
#define Il inline
#define pii pair<int,int>
#define re register
#define Mul multiset
#define Vt vector
#define Stk stack
#define Que queue
#define Itt iterator
#define PQ priority_queue
#define umap unordered_map
#define uset unordered_set
#define mpr make_pair
#define ft first
#define sd second
#define pb push_back
#define Mset(x,y) memset(x,y,sizeof x)
#define Mcpy(x,y) memcpy(x,y,sizeof y)
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define fdown(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define fupt(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define fdownt(i,a,b) for(int (i)=(a);(i)>(b);(i)--)
using namespace std;
//此处定义常量 
const int N=1e6+10,inf=0x3f3f3f3f,Mx=22;
//快读 
Il int read()
{
    int p=0,q=1;
    char ch=getchar();
    while(!isdigit(ch)) q=(ch==&#039;-&#039;)?-1:1,ch=getchar();
    while(isdigit(ch)) p=(p<<3)+(p<<1)+(ch^48),ch=getchar();
    return p*q;
}
//此处定义变量 
int n,k,cur,ans=inf;
int dp[N<<1][Mx];
struct node{
    int l,r;
    bool operator < (const node &kfc) const
    {
        if(l<kfc.l) return 1;
        if(l>kfc.l) return 0;
        return r<kfc.r;
    }
}a[N<<1];
//此处写函数
signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int r=0;
    n=read(),k=read();
    fup(i,1,k)
    {
        int x=read(),y=read();
        if(x<=y) a[i]={x,y};
        else a[i]={x,y+n};
    }
    sort(a+1,a+1+k),cur=1;
    fup(i,1,n<<1)
    {
        dp[i][0]=i,r=max(r,i);
        while(cur<=k&&a[cur].l<=i) r=max(r,a[cur++].r+1);
        dp[i][0]=r;
    }
    fupt(i,1,Mx) fup(j,1,n<<1) dp[j][i]=dp[dp[j][i-1]][i-1];
    fup(i,1,n<<1)
    {
        int now=0,mrfz=i;
        fdown(j,Mx-1,0) if(dp[mrfz][j]-i<n) now+=(1<<j),mrfz=dp[mrfz][j];
        if(mrfz-i>=n) ans=min(ans,now);
        else if (dp[mrfz][0]-i>=n) ans=min(ans,now+1);
    }
    if(ans>k)
    {
        printf("impossible");
        exit(0);
    }
    else printf("%d",ans);
    return 0;
}

T7 赛时打到build部分，没打完
临死前悟了
最小费用最大流
e
T8 有个同学写得还可以，张超的课多听两遍就废了
差不多吧
水完Blog
。。。