제출 #702915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702915		piOOE	Misspelling (JOI22_misspelling)	C++17	100 / 100	2782 ms	157120 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MOD = 1e9 + 7;

int sum(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}

int sub(int a, int b) {
    return a - b < 0 ? a - b + MOD : a - b;
}

void add(int &a, int b) {
    if ((a += b) >= MOD) {
        a -= MOD;
    }
}

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

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> queries[2];

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;

        queries[a > b].push_back(minmax(a, b));
    }

    vector<vector<array<int, 3>>> open(n + 1);
    vector<int> close(n + 1);

    vector<array<int, 4>> segments; //l, r, type, val

    for (int t = 0; t < 2; ++t) {
        vector<array<int, 3>> events; //cord, type, val

        for (auto [x, y]: queries[t]) {
            events.push_back({x, 1, -1});
            events.push_back({y, -1, x});
        }

        sort(events.begin(), events.end());

        multiset<int> st;

        for (int i = 0; i + 1 < events.size(); ++i) {
            if (events[i][2] == -1) {
                st.insert(events[i][0]);
            }
            if (events[i][2] != -1) {
                st.extract(events[i][2]);
            }

            if (!st.empty() && events[i][0] != events[i + 1][0]) {
                segments.push_back({events[i][0], events[i + 1][0], t, *st.rbegin()});
            }

        }
    }

    for (auto [l, r, t, val]: segments) {
        open[l].push_back({r, t, val});
        close[r] |= 1 << t;
    }

    int val[2]{};

    constexpr int A = 26;

    vector dp(A, vector<int>(n + 1)), pref(dp);

    auto rangeSum = [&](int c, int l, int r) {
        return sub(pref[c][r], l == 0 ? 0 : pref[c][l - 1]);
    };

    int cnt[2]{};

    for (int i = 1; i <= n; ++i) {
        for (int t : {0, 1}) {
            if (close[i - 1] >> t & 1) {
                val[t] = 0;
                cnt[t] -= 1;
            }
        }

        for (auto [r, t, v]: open[i - 1]) {
            assert(++cnt[t] == 1);
            assert(val[t] <= v);
            val[t] = v;
        }

        if (i > 1) {
            for (int a = 0; a < A; ++a) {
                for (int b = 0; b < A; ++b) {
                    if (a == b) {
                        continue;
                    }

                    add(dp[b][i - 1], rangeSum(a, val[a > b], i - 2));
                }
            }
        } else {
            for (int j = 0; j < A; ++j) {
                dp[j][0] = 1;
            }
        }

        for (int j = 0; j < A; ++j) {
            pref[j][i - 1] = sum(dp[j][i - 1], i == 1 ? 0 : pref[j][i - 2]);
        }
    }

    int ans = 0;

    for (int c = 0; c < A; ++c) {
        for (int i = 0; i <= n; ++i) {
            add(ans, dp[c][i]);
        }
    }

    cout << ans << '\n';

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

misspelling.cpp: In function 'int main()':
misspelling.cpp:55:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 0; i + 1 < events.size(); ++i) {
      |                         ~~~~~~^~~~~~~~~~~~~~~

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