Submission #584809

#	Time	Username	Problem	Language	Result	Execution time	Memory
584809		azberjibiou	Misspelling (JOI22_misspelling)	C++17	100 / 100	3631 ms	545452 KiB

misspelling

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ld long double
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef unsigned int uint;
using namespace std;
int dx[4]= {0, 1, 0, -1}, dy[4]= {1, 0, -1, 0};
int ddx[8]={1, 1, 0, -1, -1, -1, 0, 1}, ddy[8]={0, 1, 1, 1, 0, -1, -1, -1};
const int mxN=500005;
const int mxM=300005;
const int mxK=1000000000;
const int MOD=1e9+7;
const ll INF=1000000000000000005;
typedef struct seg_tree{
    ll seg[4*mxN]={};
    void upd(int idx, int s1, int e1, int pos, ll val)
    {
        seg[idx]=(seg[idx]+val)%MOD;
        if(s1==e1)  return;
        int mid=(s1+e1)/2;
        if(pos<=mid)    upd(2*idx, s1, mid, pos, val);
        else    upd(2*idx+1, mid+1, e1, pos, val);
    }
    ll sum(int idx, int s1, int e1, int s2, int e2)
    {
        if(s1>e2 || s2>e1)  return 0;
        if(s2<=s1 && e1<=e2)    return seg[idx];
        int mid=(s1+e1)/2;
        return sum(2*idx, s1, mid, s2, e2)+sum(2*idx+1, mid+1, e1, s2, e2);
    }
}seg_tree;
int N, M;
vector <pii> iu[mxN], ou[mxN], id[mxN], od[mxN];
set <pii> u, d;
ll dp[mxN][30][2];
seg_tree A[27];
ll ans=26;
int main()
{
    gibon
    cin >> N >> M;
    for(int i=1;i<=M;i++)
    {
        int a, b;
        cin >> a >> b;
        if(a<b)
        {
            id[a+1].emplace_back(a+1, b);
            od[b+1].emplace_back(a+1, b);
        }
        else
        {
            iu[b+1].emplace_back(b+1, a+1);
            ou[a+1].emplace_back(b+1, a+1);
        }
    }
    for(int i=2;i<=N;i++)
    {
        for(pii ele : id[i])    d.insert(ele);
        for(pii ele : od[i])    d.erase(ele);
        for(pii ele : iu[i])    u.insert(ele);
        for(pii ele : ou[i])    u.erase(ele);
        int lbu=(u.empty() ? 1 : u.rbegin()->fir);
        int lbd=(d.empty() ? 1 : d.rbegin()->fir);
        for(int j=2;j<=26;j++)
        {
            if(lbd==1)  dp[i][j][1]=(dp[i][j-1][1]+1+A[j-1].sum(1, 1, N, lbd, i-1))%MOD;
            else if(lbd<i)  dp[i][j][1]=(dp[i][j-1][1]+A[j-1].sum(1, 1, N, lbd, i-1))%MOD;
            else    dp[i][j][1]=0;
        }
        for(int j=25;j>=1;j--)
        {
            if(lbu==1)  dp[i][j][0]=(dp[i][j+1][0]+1+A[j+1].sum(1, 1, N, lbu, i-1))%MOD;
            else if(lbu<i)  dp[i][j][0]=(dp[i][j+1][0]+A[j+1].sum(1, 1, N, lbu, i-1))%MOD;
            else    dp[i][j][0]=0;
        }
        for(int j=1;j<=26;j++)
        {
            A[j].upd(1, 1, N, i, (dp[i][j][0]+dp[i][j][1])%MOD);
        }
    }
    for(int i=2;i<=N;i++)   for(int j=1;j<=26;j++)  ans=(ans+dp[i][j][0]+dp[i][j][1])%MOD;
    cout << ans;
}

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