Submission #657817

#	Time	Username	Problem	Language	Result	Execution time	Memory
657817		cpp219	Misspelling (JOI22_misspelling)	C++17	100 / 100	433 ms	168236 KiB

misspelling

#include<bits/stdc++.h>
#define ll long long
#define ld double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 5e5 + 9;
const ll mod = 1e9 + 7;

ll n,m;
vector<ll> bucs[N],bucg[N];
set<ll> alives,aliveg;
ll sumg[30],sums[30],dp[N][26];

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n>>m;
    while(m--){
        ll a,b; cin>>a>>b;
        if (a < b) bucg[a].push_back(b);
        else bucs[b].push_back(a);
    }
    for (ll i = 0;i < 26;i++) dp[n][i] = 1;
    for (ll i = n - 1;i > 0;i--){
        alives.insert(i + 1); aliveg.insert(i + 1);
        for (ll j = 0;j < 26;j++)
            sumg[j] += dp[i + 1][j],
            sums[j] += dp[i + 1][j];
        for (auto x : bucg[i]){
            auto it = aliveg.lower_bound(i + 1); //debug(*it);
            while(it != aliveg.end() && (*it) <= x){
                for (ll j = 0;j < 26;j++) sumg[j] -= dp[(*it)][j];
                it = aliveg.erase(it);
            }
            //exit(0);
        }
        //exit(0);
        for (auto x : bucs[i]){
            auto it = alives.lower_bound(i + 1);
            while(it != alives.end() && (*it) <= x){
                for (ll j = 0;j < 26;j++) sums[j] -= dp[(*it)][j];
                it = alives.erase(it);
            }
        }
        ll cur = 0;
        for (ll j = 0;j < 26;j++)
            dp[i][j] += cur,cur += sums[j];
        cur = 0;
        for (ll j = 25;j >= 0;j--)
            dp[i][j] += cur,cur += sumg[j];
        for (ll j = 0;j < 26;j++) dp[i][j] = (dp[i][j] + 1 + mod)%mod;
    }
    ll ans = 0;
    for (ll j = 0;j < 26;j++) ans = (ans + dp[1][j])%mod;
    cout<<ans;
}
/* be confident */

Compilation message (stderr)

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

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