Submission #2932113

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
int n,m,k;
ll dp[2][805][805];
vector<int>cm;
map<int,int>p;
P a[205];
int main(void){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        cm.PB(x);
        cm.PB(y);
        a[i]=P(x,y);
    }
    cm.PB(1);
    cm.PB(n);
    sort(cm.begin(),cm.end());
    cm.erase(unique(cm.begin(),cm.end()),cm.end());
    k=cm.size();
    for(int i=0;i<k-1;i++)if(cm[i]+1<cm[i+1])cm.PB(cm[i]+1);
    sort(cm.begin(),cm.end());
    cm.erase(unique(cm.begin(),cm.end()),cm.end());
    k=cm.size();
    for(int i=0;i<k;i++)p[cm[i]]=i;
    for(int i=0;i<m;i++){
        a[i].F=p[a[i].F];
        a[i].S=p[a[i].S];
    }
    sort(a,a+m);
    dp[0][0][0]=1;
    for(int i=0;i<m;i++){
        int u=(i+1)%2;
        for(int j=0;j<=k;j++)for(int l=0;l<=k;l++)dp[u][j][l]=0;
        for(int j=0;j<=k;j++){
            for(int l=j;l<=k;l++){
                int x=max(j,min(l,a[i].S+1)),y=max(l,a[i].S+1);
                if(a[i].F<=j)dp[u][x][y]=(dp[u][x][y]+dp[i%2][j][l])%M;
                dp[u][j][l]=(dp[u][j][l]+dp[i%2][j][l])%M;
            }
        }
    }
    cout<<dp[m%2][k][k]<<endl;
}

Submission Info

Judge Result