#include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; const int MOD = 19940417; struct Segment { int a, b; vector<pair<int, int>> points; }; bool check_adjacent(const vector<pair<int, int>>& points) { for (int i = 1; i < points.size(); ++i) { int dx = points[i].first - points[i-1].first; int dy = points[i].second - points[i-1].second; if (abs(dy) > dx || (dx - abs(dy)) % 2 != 0) { return false; } } return true; } pair<int, int> process_segment(int a, int b, const vector<pair<int, int>>& points) { int L = b - a; vector<long long> fib(L + 3, 0); fib[0] = 1; fib[1] = 1; for (int i = 2; i <= L; ++i) { fib[i] = (fib[i-1] + fib[i-2]) % MOD; } int max_h = (L) / 2; return {fib[L], max_h}; } int main() { int N, K; cin >> N >> K; vector<pair<int, int>> points(K); for (int i = 0; i < K; ++i) { cin >> points[i].first >> points[i].second; } points.emplace_back(0, 0); points.emplace_back(N, 0); sort(points.begin(), points.end()); }

#include<bits/stdc++.h> using namespace std; #define int long long int mod=19940417; int n,k,mx; void add(int &xx,int yy){xx=(xx+yy)%mod;} inline void read(int &res){ res=0; char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')res=(res<<1)+(res<<3)+c-48,c=getchar(); } inline int qpow(int ds,int zs){ if(zs0)return 1; int x=1; while(zs){ if(zs&1)x=xds%mod; ds=dsds%mod;zs>>=1; } return x; } struct node{ int x,y; }a[1000010]; bool operator<(node aa,node bb){return aa.x<bb.x;} bool operator(node aa,node bb){return aa.xbb.x&&aa.ybb.y;} int f[1000010][2]; signed main(){ read(n); read(k); for(int i=1;i<=k;i++)read(a[i].x),read(a[i].y); a[++k]=(node){0,0};a[k]=(node){n,0}; sort(&a[1],&a[k+1]);k=unique(&a[1],&a[k+1])-a-1; f[1][1]=1; for(int i=1;i<k;i){ int h=a[i+1].x-a[i].x-a[i+1].y-a[i].y;h>>=1; if(a[i+1].y-a[i].ya[i].x-a[i+1].x)f[i+1][1]=(f[i][1]+f[i][0])%mod; else if(a[i+1].y-a[i].ya[i+1].x-a[i].x)f[i+1][0]=(f[i][0]+(a[i].y?0:f[i][1]))%mod; else if(h<0)f[i+1][1]=f[i][0]; else if(h0)f[i+1][0]=(f[i][1]+f[i][0])%mod,f[i+1][1]=f[i][0]; else { int j=qpow(2,h-1); if(a[i+1].y)f[i+1][0]=(f[i][1]+2LL*f[i][0])j%mod; f[i+1][1]=(f[i][1]+2LLf[i][0])*j%mod; } if((f[i+1][1]||a[i+1].y0)&&(f[i][0]||a[i].y==0))mx=max(mx,(a[i+1].x+a[i+1].y-a[i].x+a[i].y)/2); } cout<<f[k][1]%mod<<" "<<mx<<endl; return 0; }

#include<bits/stdc++.h> using namespace std; #define int long long int mod=19940417; int n,k,mx; void add(int &xx,int yy){xx=(xx+yy)%mod;} inline void read(int &res){ res=0; char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')res=(res<<1)+(res<<3)+c-48,c=getchar(); } inline int qpow(int ds,int zs){ if(zs0)return 1; int x=1; while(zs){ if(zs&1)x=xds%mod; ds=dsds%mod;zs>>=1; } return x; } struct node{ int x,y; }a[1000010]; bool operator<(node aa,node bb){return aa.x<bb.x;} bool operator(node aa,node bb){return aa.xbb.x&&aa.ybb.y;} int f[1000010][2]; signed main(){ read(n); read(k); for(int i=1;i<=k;i++)read(a[i].x),read(a[i].y); a[++k]=(node){0,0};a[k]=(node){n,0}; sort(&a[1],&a[k+1]);k=unique(&a[1],&a[k+1])-a-1; f[1][1]=1; for(int i=1;i<k;i){ int h=a[i+1].x-a[i].x-a[i+1].y-a[i].y;h>>=1; if(a[i+1].y-a[i].ya[i].x-a[i+1].x)f[i+1][1]=(f[i][1]+f[i][0])%mod; else if(a[i+1].y-a[i].ya[i+1].x-a[i].x)f[i+1][0]=(f[i][0]+(a[i].y?0:f[i][1]))%mod; else if(h<0)f[i+1][1]=f[i][0]; else if(h0)f[i+1][0]=(f[i][1]+f[i][0])%mod,f[i+1][1]=f[i][0]; else { int j=qpow(2,h-1); if(a[i+1].y)f[i+1][0]=(f[i][1]+2LL*f[i][0])j%mod; f[i+1][1]=(f[i][1]+2LLf[i][0])*j%mod; } if((f[i+1][1]||a[i+1].y0)&&(f[i][0]||a[i].y==0))mx=max(mx,(a[i+1].x+a[i+1].y-a[i].x+a[i].y)/2); } cout<<f[k][1]%mod<<" "<<mx<<endl; return 0; }

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int MOD = 19940417; const int MAXN = 1005; // 假设 N 的最大值不超过 1000 struct Segment { int a, b; vector<pair<int, int>> points; }; bool check_adjacent(const vector<pair<int, int>>& points) { for (int i = 1; i < points.size(); ++i) { int dx = points[i].first - points[i-1].first; int dy = points[i].second - points[i-1].second; if (abs(dy) > dx || (dx - abs(dy)) % 2 != 0) { return false; } } return true; } pair<int, int> process_segment(int a, int b, const vector<pair<int, int>>& points) { int L = b - a; vector<long long> fib(L + 3, 0); fib[0] = 1; fib[1] = 1; for (int i = 2; i <= L; ++i) { fib[i] = (fib[i-1] + fib[i-2]) % MOD; } int max_h = (L) / 2; return {fib[L], max_h}; } int main() { int N, K; cin >> N >> K; vector<pair<int, int>> points(K); for (int i = 0; i < K; ++i) { cin >> points[i].first >> points[i].second; } points.emplace_back(0, 0); points.emplace_back(N, 0); sort(points.begin(), points.end()); }