oj.uz

답안 #927733

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
927733 2024-02-15T09:34:15 Z andrei_boaca Misspelling (JOI22_misspelling) C++17
100 / 100
 835 ms 457772 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n,m;
int lastmare[500005],lastmic[500005];
int dp[3][28][500005]; /// 0 -> egal, 1 -> mai mic, 2 -> mai mare
int spref[3][28][500005],ssuf[3][28][500005];
int rmq[2][21][500005]; /// 0 -> lastmic, 1 -> lastmare
int loga[500005];
int getmax(int tip,int l,int r)
{
    int lg=loga[r-l+1];
    return max(rmq[tip][lg][l],rmq[tip][lg][r-(1<<lg)+1]);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a<b)
            lastmic[a]=max(lastmic[a],b);
        if(a>b)
            lastmare[b]=max(lastmare[b],a);
    }
    for(int i=1;i<=n;i++)
    {
        for(int bit=0;bit<=20;bit++)
            if((1<<bit)<=i)
                loga[i]=bit;
        rmq[0][0][i]=lastmic[i];
        rmq[1][0][i]=lastmare[i];
    }
    for(int tip=0;tip<=1;tip++)
        for(int j=1;j<=20;j++)
            for(int i=1;i<=n;i++)
            {
                rmq[tip][j][i]=rmq[tip][j-1][i];
                int poz=i+(1<<(j-1));
                if(poz<=n)
                    rmq[tip][j][i]=max(rmq[tip][j][i],rmq[tip][j-1][poz]);
            }
    for(int i=1;i<=26;i++)
        dp[2][i][1]=1;
    for(int tip=1;tip<=2;tip++)
    {
        int suma=0;
        for(int c=1;c<=26;c++)
        {
            suma=(suma+dp[tip][c][1])%mod;
            spref[tip][c][1]=(spref[tip][c][0]+suma)%mod;
        }
    }
    for(int tip=1;tip<=2;tip++)
    {
        int suma=0;
        for(int c=26;c>=1;c--)
        {
            suma=(suma+dp[tip][c][1])%mod;
            ssuf[tip][c][1]=(ssuf[tip][c][0]+suma)%mod;
        }
    }
    for(int i=2;i<=n;i++)
    {
        int pmare=i,pmic=i;
        /// mai mare
        int st=1;
        int dr=i-1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(getmax(0,mij,i-1)<i)
            {
                pmare=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        /// mai mic
        st=1;
        dr=i-1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(getmax(1,mij,i-1)<i)
            {
                pmic=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        for(int c=1;c<=26;c++)
        {
            dp[0][c][i]=(1LL*dp[0][c][i-1]+1LL*dp[1][c][i-1]+1LL*dp[2][c][i-1])%mod;

            int x=(spref[1][c-1][i-1]-spref[1][c-1][pmic-1]+mod)%mod;
            int y=(spref[2][c-1][i-1]-spref[2][c-1][pmic-1]+mod)%mod;
            dp[1][c][i]=(x+y)%mod;
            x=(ssuf[1][c+1][i-1]-ssuf[1][c+1][pmare-1]+mod)%mod;
            y=(ssuf[2][c+1][i-1]-ssuf[2][c+1][pmare-1]+mod)%mod;
            dp[2][c][i]=(x+y)%mod;
        }
        for(int tip=1;tip<=2;tip++)
        {
            int suma=0;
            for(int c=1;c<=26;c++)
            {
                suma=(suma+dp[tip][c][i])%mod;
                spref[tip][c][i]=(spref[tip][c][i-1]+suma)%mod;
            }
        }
        for(int tip=1;tip<=2;tip++)
        {
            int suma=0;
            for(int c=26;c>=1;c--)
            {
                suma=(suma+dp[tip][c][i])%mod;
                ssuf[tip][c][i]=(ssuf[tip][c][i-1]+suma)%mod;
            }
        }
    }
    int ans=0;
    for(int c=1;c<=26;c++)
    {
        ans=(ans+dp[0][c][n])%mod;
        ans=(ans+dp[1][c][n])%mod;
        ans=(ans+dp[2][c][n])%mod;
    }
    cout<<ans;
    return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 134992 KB Output is correct
2 Correct 16 ms 134988 KB Output is correct
3 Correct 16 ms 135000 KB Output is correct
4 Correct 17 ms 134916 KB Output is correct
5 Correct 16 ms 134956 KB Output is correct
6 Correct 16 ms 135004 KB Output is correct
7 Correct 16 ms 135004 KB Output is correct
8 Correct 16 ms 135000 KB Output is correct
9 Correct 16 ms 134980 KB Output is correct
10 Correct 16 ms 135180 KB Output is correct
11 Correct 17 ms 135004 KB Output is correct
12 Correct 16 ms 135036 KB Output is correct
13 Correct 16 ms 135004 KB Output is correct
14 Correct 17 ms 135004 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 134992 KB Output is correct
2 Correct 16 ms 134988 KB Output is correct
3 Correct 16 ms 135000 KB Output is correct
4 Correct 17 ms 134916 KB Output is correct
5 Correct 16 ms 134956 KB Output is correct
6 Correct 16 ms 135004 KB Output is correct
7 Correct 16 ms 135004 KB Output is correct
8 Correct 16 ms 135000 KB Output is correct
9 Correct 16 ms 134980 KB Output is correct
10 Correct 16 ms 135180 KB Output is correct
11 Correct 17 ms 135004 KB Output is correct
12 Correct 16 ms 135036 KB Output is correct
13 Correct 16 ms 135004 KB Output is correct
14 Correct 17 ms 135004 KB Output is correct
15 Correct 16 ms 135004 KB Output is correct
16 Correct 16 ms 135000 KB Output is correct
17 Correct 17 ms 135004 KB Output is correct
18 Correct 16 ms 135260 KB Output is correct
19 Correct 17 ms 135260 KB Output is correct
20 Correct 18 ms 135004 KB Output is correct
21 Correct 17 ms 135096 KB Output is correct
22 Correct 18 ms 135004 KB Output is correct
23 Correct 16 ms 135004 KB Output is correct
24 Correct 16 ms 135032 KB Output is correct
25 Correct 17 ms 135004 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 135004 KB Output is correct
2 Correct 24 ms 134992 KB Output is correct
3 Correct 17 ms 135004 KB Output is correct
4 Correct 16 ms 135004 KB Output is correct
5 Correct 763 ms 451148 KB Output is correct
6 Correct 700 ms 451144 KB Output is correct
7 Correct 705 ms 457772 KB Output is correct
8 Correct 689 ms 457556 KB Output is correct
9 Correct 691 ms 457660 KB Output is correct
10 Correct 43 ms 149600 KB Output is correct
11 Correct 16 ms 135004 KB Output is correct
12 Correct 17 ms 135000 KB Output is correct
13 Correct 746 ms 457732 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 134992 KB Output is correct
2 Correct 16 ms 134988 KB Output is correct
3 Correct 16 ms 135000 KB Output is correct
4 Correct 17 ms 134916 KB Output is correct
5 Correct 16 ms 134956 KB Output is correct
6 Correct 16 ms 135004 KB Output is correct
7 Correct 16 ms 135004 KB Output is correct
8 Correct 16 ms 135000 KB Output is correct
9 Correct 16 ms 134980 KB Output is correct
10 Correct 16 ms 135180 KB Output is correct
11 Correct 17 ms 135004 KB Output is correct
12 Correct 16 ms 135036 KB Output is correct
13 Correct 16 ms 135004 KB Output is correct
14 Correct 17 ms 135004 KB Output is correct
15 Correct 16 ms 135004 KB Output is correct
16 Correct 16 ms 135000 KB Output is correct
17 Correct 17 ms 135004 KB Output is correct
18 Correct 16 ms 135260 KB Output is correct
19 Correct 17 ms 135260 KB Output is correct
20 Correct 18 ms 135004 KB Output is correct
21 Correct 17 ms 135096 KB Output is correct
22 Correct 18 ms 135004 KB Output is correct
23 Correct 16 ms 135004 KB Output is correct
24 Correct 16 ms 135032 KB Output is correct
25 Correct 17 ms 135004 KB Output is correct
26 Correct 42 ms 149328 KB Output is correct
27 Correct 47 ms 149316 KB Output is correct
28 Correct 41 ms 149328 KB Output is correct
29 Correct 45 ms 149588 KB Output is correct
30 Correct 47 ms 149744 KB Output is correct
31 Correct 109 ms 154664 KB Output is correct
32 Correct 44 ms 149652 KB Output is correct
33 Correct 43 ms 149576 KB Output is correct
34 Correct 44 ms 149792 KB Output is correct
35 Correct 104 ms 154740 KB Output is correct
36 Correct 42 ms 149376 KB Output is correct
37 Correct 44 ms 149600 KB Output is correct
38 Correct 46 ms 149560 KB Output is correct
39 Correct 42 ms 149572 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 134992 KB Output is correct
2 Correct 16 ms 134988 KB Output is correct
3 Correct 16 ms 135000 KB Output is correct
4 Correct 17 ms 134916 KB Output is correct
5 Correct 16 ms 134956 KB Output is correct
6 Correct 16 ms 135004 KB Output is correct
7 Correct 16 ms 135004 KB Output is correct
8 Correct 16 ms 135000 KB Output is correct
9 Correct 16 ms 134980 KB Output is correct
10 Correct 16 ms 135180 KB Output is correct
11 Correct 17 ms 135004 KB Output is correct
12 Correct 16 ms 135036 KB Output is correct
13 Correct 16 ms 135004 KB Output is correct
14 Correct 17 ms 135004 KB Output is correct
15 Correct 16 ms 135004 KB Output is correct
16 Correct 16 ms 135000 KB Output is correct
17 Correct 17 ms 135004 KB Output is correct
18 Correct 16 ms 135260 KB Output is correct
19 Correct 17 ms 135260 KB Output is correct
20 Correct 18 ms 135004 KB Output is correct
21 Correct 17 ms 135096 KB Output is correct
22 Correct 18 ms 135004 KB Output is correct
23 Correct 16 ms 135004 KB Output is correct
24 Correct 16 ms 135032 KB Output is correct
25 Correct 17 ms 135004 KB Output is correct
26 Correct 18 ms 135004 KB Output is correct
27 Correct 24 ms 134992 KB Output is correct
28 Correct 17 ms 135004 KB Output is correct
29 Correct 16 ms 135004 KB Output is correct
30 Correct 763 ms 451148 KB Output is correct
31 Correct 700 ms 451144 KB Output is correct
32 Correct 705 ms 457772 KB Output is correct
33 Correct 689 ms 457556 KB Output is correct
34 Correct 691 ms 457660 KB Output is correct
35 Correct 43 ms 149600 KB Output is correct
36 Correct 16 ms 135004 KB Output is correct
37 Correct 17 ms 135000 KB Output is correct
38 Correct 746 ms 457732 KB Output is correct
39 Correct 42 ms 149328 KB Output is correct
40 Correct 47 ms 149316 KB Output is correct
41 Correct 41 ms 149328 KB Output is correct
42 Correct 45 ms 149588 KB Output is correct
43 Correct 47 ms 149744 KB Output is correct
44 Correct 109 ms 154664 KB Output is correct
45 Correct 44 ms 149652 KB Output is correct
46 Correct 43 ms 149576 KB Output is correct
47 Correct 44 ms 149792 KB Output is correct
48 Correct 104 ms 154740 KB Output is correct
49 Correct 42 ms 149376 KB Output is correct
50 Correct 44 ms 149600 KB Output is correct
51 Correct 46 ms 149560 KB Output is correct
52 Correct 42 ms 149572 KB Output is correct
53 Correct 692 ms 453344 KB Output is correct
54 Correct 702 ms 452536 KB Output is correct
55 Correct 752 ms 457572 KB Output is correct
56 Correct 779 ms 457644 KB Output is correct
57 Correct 701 ms 457640 KB Output is correct
58 Correct 835 ms 457756 KB Output is correct
59 Correct 764 ms 457672 KB Output is correct
60 Correct 750 ms 457720 KB Output is correct
61 Correct 633 ms 447244 KB Output is correct
62 Correct 711 ms 456028 KB Output is correct
63 Correct 732 ms 454272 KB Output is correct
64 Correct 698 ms 452724 KB Output is correct