제출 #544499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544499		model_code	Misspelling (JOI22_misspelling)	C++17	100 / 100	789 ms	397488 KiB

misspelling

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rrep(i,l,r) for(int i=l;i<=r;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define unq(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define mod 1000000007
#define ad(a,b) a=(a+b)%mod;
#define mul(a,b) a=a*b%mod;

#define N 500010
#define M 500010
#define K 26

class STACK{
    private:
    stack<pll> s;
    public:
    ll sum;
    void init(){
        sum=0;
    }
    void add(ll pos,ll val){
        s.push(mp(pos,val));
        ad(sum,val);
    }
    void ers(ll ul){//erase[-inf,ul]
        while(!s.empty()){
            if(s.top().first>ul)break;
            ad(sum,-s.top().second);
            s.pop();
        }
    }
};
STACK stc[26][2];

ll n,m;
ll a[M],b[M];
ll maxb[N][2];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m;
    rep(i,n){
        rep(f,2){
            maxb[i][f]=-1e18;
        }
    }
    rep(i,m){
        cin>>a[i]>>b[i];
        a[i]--,b[i]--;
        ll x=min(a[i],b[i]);
        ll y=max(a[i],b[i]);
        chmax(maxb[x][a[i]<b[i]],y);
    }
	rep(c,26)rep(f,2)stc[c][f].init();
    rep(c,26){
        stc[c][0].add(n,1);
	}
    for(int pos=n-1;pos>0;pos--){
        ll sums[26][2];
        rep(c,26)rep(ud,2)sums[c][ud]=stc[c][ud].sum;
        rep(c,26)rep(ud,2){
            stc[c][ud].ers(maxb[pos-1][ud^1]);
        }
		if(pos>maxb[pos-1][0]){
			ll rui=0;
			rep(c,26){
				stc[c][1].add(pos,rui);
				rep(ud,2){
					ad(rui,sums[c][ud]);
				}
			}
		}
		if(pos>maxb[pos-1][1]){
			ll rui=0;
			per(c,26){
				stc[c][0].add(pos,rui);
				rep(ud,2){
					ad(rui,sums[c][ud]);
				}
			}
		}
    }
    ll ans=0;
    rep(c,26)rep(ud,2){
		ad(ans,stc[c][ud].sum);
    }
    if(ans<0)ans+=mod;
    cout<<ans<<endl;
}

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