Submission #990864

#	Time	Username	Problem	Language	Result	Execution time	Memory
990864		vjudge1	Misspelling (JOI22_misspelling)	C++17	100 / 100	615 ms	166240 KiB

misspelling

// Author: Ivan Teo
// Created: Fri May 31 20:45:47 2024

#define TASKNAME "misspelling"
#include <bits/stdc++.h>
using namespace std;

#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define el cerr << "\n=========================================\n"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
    assert(l <= r);
    return uniform_int_distribution<int> (l, r)(rng);
}

const int N = 5e5 + 5;
const int mod = 1e9 + 7;
vector<tuple<int, int, int>> ev[N];
int f[N][26];
int n, m;

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

void solve()
{
    cin >> n >> m;
    fore(i, 1, m)
    {
        int a, b;
        cin >> a >> b;
        if (a == b) continue;
        a++, b++;
        bool flag = (a < b);
        if (a > b) swap(a, b);
        ev[a].pb(flag, a - 1, 1);
        ev[b].pb(flag, a - 1, -1);
    }
    array<multiset<int, greater<int>>, 2> s;
    for (auto [flag, a, type] : ev[1]) s[flag].insert(a);
    fore(i, 0, 25) f[1][i] = i + 1;
    fore(i, 2, n)
    {
        for (auto [flag, a, type] : ev[i])
        {
            if (type == 1) s[flag].insert(a);
            else
            {
                auto it = s[flag].find(a);
                s[flag].erase(it);
            }
        }
        int pre[2] = {0};
        fore(j, 0, 1) if (!s[j].empty()) pre[j] = *s[j].begin();
        // cout << pre[0] << ' ' << pre[1] << '\n';
        fore(d, 0, 25)
        {
            if (d) f[i][d] = (f[i][d] + f[i - 1][d - 1] - f[pre[0]][d - 1] + mod) % mod;
            f[i][d] = (f[i][d] + (f[i - 1][25] - f[pre[1]][25] - f[i - 1][d] + f[pre[1]][d]) + mod * 2) % mod;
            if (d) f[i][d] = (f[i][d] + f[i][d - 1]) % mod;
        }
        fore(d, 0, 25) f[i][d]=(f[i][d]+f[i-1][d])%mod;
    }
    cout << f[n][25];
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("in", "r"))
        freopen("in", "r", stdin);
    if (fopen(TASKNAME ".inp", "r"))
    {
        freopen(TASKNAME ".inp", "r", stdin);
        freopen(TASKNAME ".out", "w", stdout);
    }
    int tc = 1;
    // cin >> tc;
    while (tc--)
        solve();
    el, cerr << "Execution Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s", el;
    return 0;
}

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen("in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
misspelling.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(TASKNAME ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
misspelling.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(TASKNAME ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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