题解

#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());

for (auto& p : points) {
    if ((p.first == 0 || p.first == N) && p.second != 0) {
        cout << "0 0" << endl;
        return 0;
    }
}

for (int i = 0; i < points.size(); ++i) {
    if (i > 0 && points[i].first == points[i-1].first) {
        if (points[i].second != points[i-1].second) {
            cout << "0 0" << endl;
            return 0;
        }
    }
}

vector<pair<int, int>> unique_points;
for (int i = 0; i < points.size(); ++i) {
    if (i == 0 || points[i].first != points[i-1].first) {
        unique_points.push_back(points[i]);
    }
}
points = unique_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) {
        cout << "0 0" << endl;
        return 0;
    }
}

vector<Segment> segments;
for (int i = 1; i < points.size(); ++i) {
    int a = points[i-1].first;
    int b = points[i].first;
    if (points[i-1].second != 0 || points[i].second != 0) {
        cout << "0 0" << endl;
        return 0;
    }
    vector<pair<int, int>> seg_pts;
    for (auto& p : points) {
        if (p.first > a && p.first < b) {
            seg_pts.push_back(p);
        }
    }
    segments.push_back({a, b, seg_pts});
}

long long ans_count = 1;
int ans_max = 0;
for (auto& seg : segments) {
    if (!seg.points.empty()) {
        cout << "0 0" << endl;
        return 0;
    }
    int a = seg.a;
    int b = seg.b;
    auto res = process_segment(a, b, seg.points);
    ans_count = ans_count * res.first % MOD;
    ans_max = max(ans_max, res.second);
}

cout << ans_count << " " << ans_max << endl;
return 0;
}