Submission #70852314

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

constexpr long long mod = 1e9 + 7;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> in1, in2;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if(a < b){
            in1.emplace_back(a, b - 1);
        }
        else{
            in2.emplace_back(b, a - 1);
        }
    }

    auto sub = [&](vector<pair<int, int>> &in){
        multiset<int> st;
        st.insert(-1);
        int sz = in.size();
        vector<int> res(n - 1);
        vector<vector<int>> add(n - 1), era(n - 1);
        for(auto [l, r]: in){
            add[l].emplace_back(l);
            era[r].emplace_back(l);
        }
        for(int i = 0; i < n - 1; i++){
            for(int ad: add[i]){
                st.insert(ad);
            }
            auto itr = st.end();
            res[i] = *(--itr);
            for(int er: era[i]){
                st.erase(st.find(er));
            }
        }
        return res;
    };
    vector<int> mxl1 = sub(in1), mxl2 = sub(in2);

    vector<vector<long long>> dp(26, vector<long long>(n, 0));
    vector<vector<long long>> dpsum(26, vector<long long>(n + 1, 0));
    for(int i = 0; i < 26; i++){
        dp[i][0] = 1;
        dpsum[i][1] = 1;
    }
    for(int i = 0; i < n - 1; i++){
        int left;
        long long s;

        // < にしたい
        left = mxl1[i] + 1;
        s = 0;
        for(int j = 0; j < 26; j++){
            dp[j][i + 1] += s;
            s += dpsum[j][i + 1] - dpsum[j][left];
            s %= mod;
        }

        // > にしたい
        left = mxl2[i] + 1;
        s = 0;
        for(int j = 25; j >= 0; j--){
            dp[j][i + 1] += s;
            s += dpsum[j][i + 1] - dpsum[j][left];
            s %= mod;
        }

        for(int j = 0; j < 26; j++){
            dpsum[j][i + 2] = dpsum[j][i + 1] + dp[j][i + 1];
            dpsum[j][i + 2] %= mod;
        }
    }

    long long ans = 0;
    for(int i = 0; i < 26; i++){
        for(int j = 0; j < n; j++){
            ans += dp[i][j];
            ans %= mod;
        }
    }

    if(ans < 0) ans += mod;
    cout << ans << endl;
}

/*
dif[0], dif[1], ..., dif[n - 2] を決める
dif[i] \in {>, =, <} : それぞれ s[i], s[i + 1] の関係
*/

/*
dp[最後の = 以外が > か < か][その場所][今の文字] とする dp をしたい

in1 の区間 [l, r] について
dif[l, r] について < は > より後に出てくる

in2 の区間 [l, r] について
dif[l, r] について > は < より後に出てくる

dif[p] = < としたい
in1 かつ l <= p <= r なる [l, r] について l の max を取る
[その場所] が l 未満 -> 遷移ダメ
それ以外 ok
l <= p' < p で dif[p'] = > : 当然 ok
               dif[p'] = < : p' に < を置いてるので ok

dif[p] = > としたい
in2 かつ l <= p <= r なる [l, r] について l の max を取る
[その場所] が l 未満 -> 遷移ダメ
それ以外 ok
l <= p' < p で dif[p'] = > : p' に > を置いてるので ok
               dif[p'] = < : 当然 ok

結局 dp[最後に = でなかった場所][今の文字] として良さそう

各 p について in1 かつ l <= p <= r なる [l, r] について l の max を取りたい
multiset でできそう
*/

Submission Info

Compile Error

Main.cpp: In lambda function:
Main.cpp:29:13: warning: unused variable ‘sz’ [-Wunused-variable]
   29 |         int sz = in.size();
      |             ^~

Judge Result