제출 #986876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986876		AlperenT_	Misspelling (JOI22_misspelling)	C++17	100 / 100	394 ms	166648 KiB

misspelling

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <ll,ll>
#define PII pair<pii , pii>
#define ld long double
#define ll long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
const int maxn = 6e5 + 10  , N = 1e5 +1 , lg = 20 , maxq = 202   , inf = 1e9  , maxk = 2022  , mod =1e9+7;
ll dp[maxn][28] , s[28] ;
vector <pii> vec[maxn] ;
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);   
    int n , m ;
    cin >> n >> m ;
    rep(i ,1 ,m){
        int l , r;
        cin >>  l>> r; 
        if(l == r)continue ;
        int t =1 ;
        if(l > r){
            t = -1;
            swap(l, r);
        }
        vec[l].pb({r,t});
    }
    set <int> t[2] ;
    per(i , n , 1){
        for(auto [r,ty] : vec[i]){
            if(ty == 1){
                while(sz(t[0]) && (*t[0].begin()) <= r){
                    int v= (*t[0].begin()) ;
                    t[0].erase(v); 
                    rep(j , 1 , 26){
                        s[j] = (s[j] - dp[v][j-1] + mod)%mod ;
                    }
                }
            }else{
                while(sz(t[1]) && (*t[1].begin()) <= r){
                    int v = (*t[1].begin()) ;
                    t[1].erase(v) ;
                    rep(j , 1 , 26){
                        s[j] = (s[j] - (dp[v][26] - dp[v][j] + mod) + 2*mod)%mod ;
                    }
                }
            }
        }
        rep(j , 1 , 26){
            dp[i][j] = (s[j] + 1 + dp[i][j-1])%mod  ;
        }
        rep(j , 1 , 26){
            s[j] = (s[j] + dp[i][26] - dp[i][j] + dp[i][j-1]+mod)%mod ;
        }
        t[0].insert(i);
        t[1].insert(i);
    }
    cout << dp[1][26] << "\n"; 
}
/*

*/

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