Submission #592365

#	Time	Username	Problem	Language	Result	Execution time	Memory
592365		balbit	Misspelling (JOI22_misspelling)	C++14	100 / 100	279 ms	124464 KiB

misspelling

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=n-1;i>=0;--i)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int mod = 1e9+7;
const int maxn = 5e5+5;
#define dec DECCCC
int inc[maxn], dec[maxn];

void prune(vector<pii> v, bool doinc) {
    for (pii &p : v) {
        p.f = -p.f; p.s = -p.s; swap(p.f, p.s);
    }
    sort(ALL(v), [&](pii a, pii b){return a.s!=b.s?a.s < b.s : a.f < b.f;});
    vector<pii> R;
    for (pii p : v) {
        while (SZ(R) && p.f < R.back().f) {
            R.pop_back();
        }
        if (SZ(R)) MX(p.f, R.back().s+1);
        if (p.f <= p.s) {
            bug(p.f, p.s);
            (doinc?inc:dec)[-p.s] = -p.f;
        R.pb({p.f, p.s});
        }
    }
}

int dpi[maxn][26], dpd[maxn][26];
inline void ADD(int &a, int b) {
    a = (a+b)>=mod?a+b-mod:a+b;
}
void eat(int *a, int *b, int tp) { // 1: i eats bigger, 0: eq, -1: i eats smaller
    if (tp == 1) {
        int tmp = 0;
        RREP(j,26) {
            ADD(a[j], tmp);
            ADD(tmp, b[j]);
        }
    }else if (tp == -1) {
        int tmp = 0;
        REP(j,26) {
            ADD(a[j], tmp);
            ADD(tmp, b[j]);
        }
    }else{
        REP(j,26) {
            ADD(a[j], b[j]);
        }
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);

    int n,m; cin>>n>>m;

    vector<pii> vinc, vdec;
    REP(i,m) {
        int a,b; cin>>a>>b; --a; --b;
        if (a < b) vinc.pb({a,b-1});
        else vdec.pb({b,a-1});
    }

    memset(inc, -1, sizeof inc);
    memset(dec, -1, sizeof dec);

    prune(vinc, 1);
    prune(vdec, 0);

    REP(j,26) dpi[n-1][j]=1;

    for (int i = n-2; i>=0; --i) {
        bug(i, inc[i], dec[i]);

        if (dec[i] == -1) {
            eat(dpi[i], dpi[i+1], 1);
            eat(dpi[i], dpd[i+1], 1);
        }
        if (inc[i] == -1) {
            eat(dpd[i], dpi[i+1], -1);
            eat(dpd[i], dpd[i+1], -1);
        }

        if (inc[i] == -1 && dec[i] == -1) {
            eat(dpi[i], dpi[i+1], 0);
            eat(dpd[i], dpd[i+1], 0);
        }
        else if (inc[i] == -1) {
            eat(dpd[i], dpd[i+1], 0);
            eat(dpi[i], dpi[dec[i]+1], 0);
        }else if (dec[i] == -1) {
            eat(dpi[i], dpi[i+1], 0);
            eat(dpd[i], dpd[inc[i]+1], 0);
        }else{
            eat(dpi[i], dpi[dec[i]+1], 0);
            eat(dpd[i], dpd[inc[i]+1], 0);
        }
    }
    int re = 0;

    REP(j,26) {
        bug(j,dpi[0][j], dpd[0][j]);
        ADD(re, dpi[0][j]);
        ADD(re, dpd[0][j]);
    }

    cout<<re<<endl;

}

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