Submission #596246

#	Time	Username	Problem	Language	Result	Execution time	Memory
596246		spacewalker	Misspelling (JOI22_misspelling)	C++14	100 / 100	1167 ms	413096 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;

struct DPValueList {
    vector<pair<int, ll>> values;
    ll sum;
    DPValueList() : sum(0) {}
    void reg(int i, ll v) {
        sum = (sum + v) % MOD;
        values.emplace_back(i, v);
    }
    void prune(int i) {
        while (!values.empty() && values.back().first < i) {
            sum = (sum + MOD - values.back().second) % MOD;
            values.pop_back();
        }
    }
};

int main() {
    int n, m; scanf("%d %d", &n, &m);
    vector<vector<int>> firstIncEnds(n), firstDecEnds(n);
    for (int i = 0; i < m; ++i) {
        int a, b; scanf("%d %d", &a, &b); --a; --b;
        // a < b means first change is an increase
        if (a < b) firstDecEnds[a].push_back(b);
        else firstIncEnds[b].push_back(a);
    }
    // simplify the constraints
    for (int i = 0; i < n; ++i) {
        if (firstIncEnds[i].size() > 0) {
            firstIncEnds[i] = {*max_element(begin(firstIncEnds[i]), end(firstIncEnds[i]))};
        }
        if (firstDecEnds[i].size() > 0) {
            firstDecEnds[i] = {*max_element(begin(firstDecEnds[i]), end(firstDecEnds[i]))};
        }
        if (firstIncEnds[i].size() > 0 && firstDecEnds[i].size() > 0) {
            int first = min(firstIncEnds[i][0], firstDecEnds[i][0]), secnd = max(firstIncEnds[i][0], firstDecEnds[i][0]);
            if (first < secnd) {
                if (firstIncEnds[i][0] == secnd) firstIncEnds[first].push_back(secnd);
                if (firstDecEnds[i][0] == secnd) firstDecEnds[first].push_back(secnd);
                firstIncEnds[i][0] = firstDecEnds[i][0] = first;
            }
        }
    }
    //vector<vector<ll>> lastInc(n, vector<ll>(26)), lastDec(n, vector<ll>(26));
    vector<DPValueList> lastInc(26), lastDec(26);
    for (int i = 0; i < 26; ++i) lastInc[i].reg(n-1, 1);
    for (int i = n - 2; i >= 0; --i) {
        // count the current sols
        vector<ll> currEndAt(26);
        for (int d = 0; d < 26; ++d) {
            currEndAt[d] += lastInc[d].sum + lastDec[d].sum;
            currEndAt[d] %= MOD;
        }
        // update the counts for n
        for (int d = 0; d < 26; ++d) {
            ll curLastInc = 0, curLastDec = 0;
            for (int dnext = 0; dnext < 26; ++dnext) {
                if (d < dnext && firstDecEnds[i].size() == 0) { // increase
                    curLastInc += currEndAt[dnext];
                }
                if (d > dnext && firstIncEnds[i].size() == 0) { // decrease
                    curLastDec += currEndAt[dnext];
                }
            }
            lastInc[d].reg(i, curLastInc % MOD);
            lastDec[d].reg(i, curLastDec % MOD);
        }
        // eliminate all sols that don't follow any existing constraints
        if (firstIncEnds[i].size() > 0) {
            // printf("constraint first inc %d %d\n", i, firstIncEnds[i][0]);
            for (int d = 0; d < 26; ++d) {
                lastDec[d].prune(firstIncEnds[i][0]);
            }
        }
        if (firstDecEnds[i].size() > 0) {
            // printf("constraint first dec %d %d\n", i, firstDecEnds[i][0]);
            for (int d = 0; d < 26; ++d) {
                lastInc[d].prune(firstDecEnds[i][0]);
            }
        }
        for (int d = 0; d < 26; ++d) {
           // printf("%d %d inc %lld dec %lld\n", i, d, lastInc[i][d], lastDec[i][d]);
        }
    }
    ll ans = 0;
    for (int d = 0; d < 26; ++d) {
        ans = (ans + lastInc[d].sum + lastDec[d].sum) % MOD;
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:24:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     int n, m; scanf("%d %d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~~
misspelling.cpp:27:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         int a, b; scanf("%d %d", &a, &b); --a; --b;
      |                   ~~~~~^~~~~~~~~~~~~~~~~

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