Submission #584906

#	Time	Username	Problem	Language	Result	Execution time	Memory
584906		CodePlatina	Misspelling (JOI22_misspelling)	C++17	100 / 100	633 ms	359496 KiB

misspelling

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
const int INF = (int)1e9 + 7;

using namespace std;

vector<int> A[505050];
vector<int> B[505050];
priority_queue<pii> C, D;
long long dp[505050][26];
long long L[505050][26];
long long R[505050][26];
long long S[505050];

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

    int n, m; cin >> n >> m;
    for(int i = 0; i < m; ++i)
    {
        int x, y; cin >> x >> y;
        if(x > y) A[y].push_back(x);
        else B[x].push_back(y);
    }

    for(int i = 0; i < 26; ++i) dp[1][i] = 1, L[1][i] = i, R[1][i] = 25 - i, S[1] = 26;
    for(int i = 1; i < n; ++i)
    {
        for(auto j : A[i]) C.push({i, j});
        for(auto j : B[i]) D.push({i, j});
        while(C.size() && C.top().ss <= i) C.pop();
        while(D.size() && D.top().ss <= i) D.pop();
        int x = (C.size() ? C.top().ff : 0);
        int y = (D.size() ? D.top().ff : 0);
        int z = max(x, y);
        for(int j = 0; j < 26; ++j) dp[i + 1][j] = (2 * INF + dp[i][j] + (S[i] - S[z]) - (dp[i][j] - dp[z][j])) % INF;
        if(x > y) for(int j = 0; j < 26; ++j) dp[i + 1][j] = (INF + dp[i + 1][j] + (L[x][j] - L[y][j])) % INF;
        if(x < y) for(int j = 0; j < 26; ++j) dp[i + 1][j] = (INF + dp[i + 1][j] + (R[y][j] - R[x][j])) % INF;
        for(int j = 1; j < 26; ++j) L[i + 1][j] = (L[i + 1][j - 1] + dp[i + 1][j - 1]) % INF;
        for(int j = 24; j >= 0; --j) R[i + 1][j] = (R[i + 1][j + 1] + dp[i + 1][j + 1]) % INF;
        for(int j = 0; j < 26; ++j) S[i + 1] = (S[i + 1] + dp[i + 1][j]) % INF;
    }

    cout << S[n];
}

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