Submission #862522

#	Time	Username	Problem	Language	Result	Execution time	Memory
862522		boris_mihov	Misspelling (JOI22_misspelling)	C++17	8 / 100	4062 ms	83284 KiB

misspelling

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <bitset>
#include <stack>

typedef long long llong;
const int MAXN = 500000 + 10;
const int ALPHABET = 26;
const int MOD = 1e9 + 7;

int n, m;
int l[MAXN];
int r[MAXN];
int type[MAXN];
int dp[MAXN][ALPHABET];
std::bitset <MAXN> active[ALPHABET][ALPHABET]; 
std::vector <int> begin[MAXN];

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

void sub(int &num, int &val)
{
    num -= val;
    if (num < 0) num += MOD;
}

void solve()
{
    for (int i = ALPHABET - 1 ; i >= 0 ; --i)
    {
        dp[n][i] = 1;
    }

    for (int pos = n - 1 ; pos >= 1 ; --pos)
    {
        for (int letter = 0 ; letter < ALPHABET ; ++letter)
        {
            dp[pos][letter] = dp[pos + 1][letter];
            for (int addL = 0 ; addL < ALPHABET ; ++addL)
            {
                if (addL == letter)
                {
                    continue;
                }

                add(dp[pos][letter], dp[pos + 1][addL]);
                active[letter][addL][pos + 1] = 1;
            }

            for (const int &j : begin[pos])
            {
                if (type[j] == 1)
                {
                    for (int remL = letter + 1 ; remL < ALPHABET ; ++remL)
                    {
                        while (active[letter][remL].count() && active[letter][remL]._Find_first() <= r[j])
                        {
                            sub(dp[pos][letter], dp[active[letter][remL]._Find_first()][remL]);
                            active[letter][remL][active[letter][remL]._Find_first()] = 0;
                        }
                    }
                } else
                {
                    for (int remL = letter - 1 ; remL >= 0 ; --remL)
                    {
                        while (active[letter][remL].count() && active[letter][remL]._Find_first() <= r[j])
                        {
                            sub(dp[pos][letter], dp[active[letter][remL]._Find_first()][remL]);
                            active[letter][remL][active[letter][remL]._Find_first()] = 0;
                        }
                    }
                }
            }
        }
    }

    int sum = 0;
    for (int i = 0 ; i < 26 ; ++i)
    {
        sum += dp[1][i];
        if (sum >= MOD) sum -= MOD;
    }

    std::cout << sum << '\n';
}

void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> l[i] >> r[i];
        type[i] = 1;

        if (l[i] > r[i])
        {
            std::swap(l[i], r[i]);
            type[i] = 2;
        }

        begin[l[i]].push_back(i);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

misspelling.cpp: In function 'void solve()':
misspelling.cpp:63:99: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |                         while (active[letter][remL].count() && active[letter][remL]._Find_first() <= r[j])
      |                                                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
misspelling.cpp:73:99: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |                         while (active[letter][remL].count() && active[letter][remL]._Find_first() <= r[j])
      |                                                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

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