제출 #938808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938808		alextodoran	Misspelling (JOI22_misspelling)	C++17	100 / 100	1949 ms	79296 KiB

misspelling

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 500000;
const int M_MAX = 500000;
const int MOD = (int) 1e9 + 7;

int N, M;
struct Restrict {
    int l, r;
    bool type;
};
bool operator < (const Restrict &a, const Restrict &b) {
    return a.r > b.r;
}
Restrict R[M_MAX + 2];
int dp[N_MAX + 2][26];

int maxL[N_MAX + 2][2];

void add (int &x, const int &y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}
void sub (int &x, const int &y) {
    x -= y;
    if (x < 0) {
        x += MOD;
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        cin >> R[i].l >> R[i].r;
        if (R[i].l > R[i].r) {
            swap(R[i].l, R[i].r);
            R[i].type = 1;
        } else {
            R[i].type = 0;
        }
    }
    set <int> s[2];
    sort(R + 1, R + M + 1);
    for (int i = N - 1, j = 1; i >= 1; i--) {
        while (j <= M && R[j].r > i) {
            s[R[j].type].insert(R[j].l);
            j++;
        }
        for (bool t : {0, 1}) {
            while (s[t].empty() == false && *s[t].rbegin() > i) {
                s[t].erase(prev(s[t].end()));
            }
            if (s[t].empty() == false) {
                maxL[i][t] = max(maxL[i][t], *s[t].rbegin());
            }
        }
    }
    for (int c = 0; c < 26; c++) {
        dp[0][c] = 1;
    }
    for (int i = 1; i <= N - 1; i++) {
        for (int c = 0; c < 26; c++) {
            for (int cj = 0; cj < 26; cj++) {
                if (c != cj) {
                    add(dp[i][c], dp[i - 1][cj]);
                }
            }
            if (maxL[i][0] > 0) {
                for (int cj = 0; cj < c; cj++) {
                    sub(dp[i][c], dp[maxL[i][0] - 1][cj]);
                }
            }
            if (maxL[i][1] > 0) {
                for (int cj = 25; cj > c; cj--) {
                    sub(dp[i][c], dp[maxL[i][1] - 1][cj]);
                }
            }
            add(dp[i][c], dp[i - 1][c]);
        }
    }
    int answer = 0;
    for (int c = 0; c < 26; c++) {
        add(answer, dp[N - 1][c]);
    }
    cout << answer << "\n";

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11