oj.uz

Submission #584809

# Submission time Handle Problem Language Result Execution time Memory
584809 2022-06-28T04:08:08 Z azberjibiou Misspelling (JOI22_misspelling) C++17
100 / 100
 3631 ms 545452 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47444 KB Output is correct
2 Correct 23 ms 47400 KB Output is correct
3 Correct 24 ms 47520 KB Output is correct
4 Correct 23 ms 47428 KB Output is correct
5 Correct 22 ms 47488 KB Output is correct
6 Correct 22 ms 47480 KB Output is correct
7 Correct 22 ms 47516 KB Output is correct
8 Correct 23 ms 47436 KB Output is correct
9 Correct 24 ms 47436 KB Output is correct
10 Correct 23 ms 47424 KB Output is correct
11 Correct 23 ms 47492 KB Output is correct
12 Correct 23 ms 47488 KB Output is correct
13 Correct 23 ms 47484 KB Output is correct
14 Correct 22 ms 47444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47444 KB Output is correct
2 Correct 23 ms 47400 KB Output is correct
3 Correct 24 ms 47520 KB Output is correct
4 Correct 23 ms 47428 KB Output is correct
5 Correct 22 ms 47488 KB Output is correct
6 Correct 22 ms 47480 KB Output is correct
7 Correct 22 ms 47516 KB Output is correct
8 Correct 23 ms 47436 KB Output is correct
9 Correct 24 ms 47436 KB Output is correct
10 Correct 23 ms 47424 KB Output is correct
11 Correct 23 ms 47492 KB Output is correct
12 Correct 23 ms 47488 KB Output is correct
13 Correct 23 ms 47484 KB Output is correct
14 Correct 22 ms 47444 KB Output is correct
15 Correct 23 ms 47596 KB Output is correct
16 Correct 23 ms 47580 KB Output is correct
17 Correct 29 ms 47624 KB Output is correct
18 Correct 26 ms 47640 KB Output is correct
19 Correct 31 ms 47696 KB Output is correct
20 Correct 25 ms 47616 KB Output is correct
21 Correct 26 ms 47700 KB Output is correct
22 Correct 28 ms 48204 KB Output is correct
23 Correct 24 ms 47680 KB Output is correct
24 Correct 26 ms 47676 KB Output is correct
25 Correct 26 ms 47700 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47460 KB Output is correct
2 Correct 31 ms 47424 KB Output is correct
3 Correct 24 ms 47444 KB Output is correct
4 Correct 24 ms 47416 KB Output is correct
5 Correct 2462 ms 533564 KB Output is correct
6 Correct 2421 ms 533588 KB Output is correct
7 Correct 2438 ms 533556 KB Output is correct
8 Correct 2406 ms 533560 KB Output is correct
9 Correct 2430 ms 533504 KB Output is correct
10 Correct 104 ms 71576 KB Output is correct
11 Correct 24 ms 47684 KB Output is correct
12 Correct 23 ms 47432 KB Output is correct
13 Correct 3264 ms 545452 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47444 KB Output is correct
2 Correct 23 ms 47400 KB Output is correct
3 Correct 24 ms 47520 KB Output is correct
4 Correct 23 ms 47428 KB Output is correct
5 Correct 22 ms 47488 KB Output is correct
6 Correct 22 ms 47480 KB Output is correct
7 Correct 22 ms 47516 KB Output is correct
8 Correct 23 ms 47436 KB Output is correct
9 Correct 24 ms 47436 KB Output is correct
10 Correct 23 ms 47424 KB Output is correct
11 Correct 23 ms 47492 KB Output is correct
12 Correct 23 ms 47488 KB Output is correct
13 Correct 23 ms 47484 KB Output is correct
14 Correct 22 ms 47444 KB Output is correct
15 Correct 23 ms 47596 KB Output is correct
16 Correct 23 ms 47580 KB Output is correct
17 Correct 29 ms 47624 KB Output is correct
18 Correct 26 ms 47640 KB Output is correct
19 Correct 31 ms 47696 KB Output is correct
20 Correct 25 ms 47616 KB Output is correct
21 Correct 26 ms 47700 KB Output is correct
22 Correct 28 ms 48204 KB Output is correct
23 Correct 24 ms 47680 KB Output is correct
24 Correct 26 ms 47676 KB Output is correct
25 Correct 26 ms 47700 KB Output is correct
26 Correct 115 ms 71756 KB Output is correct
27 Correct 125 ms 70996 KB Output is correct
28 Correct 118 ms 71036 KB Output is correct
29 Correct 116 ms 71664 KB Output is correct
30 Correct 129 ms 71584 KB Output is correct
31 Correct 498 ms 88744 KB Output is correct
32 Correct 113 ms 71580 KB Output is correct
33 Correct 107 ms 71632 KB Output is correct
34 Correct 127 ms 71852 KB Output is correct
35 Correct 693 ms 99660 KB Output is correct
36 Correct 123 ms 70128 KB Output is correct
37 Correct 122 ms 71468 KB Output is correct
38 Correct 132 ms 71032 KB Output is correct
39 Correct 143 ms 70672 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47444 KB Output is correct
2 Correct 23 ms 47400 KB Output is correct
3 Correct 24 ms 47520 KB Output is correct
4 Correct 23 ms 47428 KB Output is correct
5 Correct 22 ms 47488 KB Output is correct
6 Correct 22 ms 47480 KB Output is correct
7 Correct 22 ms 47516 KB Output is correct
8 Correct 23 ms 47436 KB Output is correct
9 Correct 24 ms 47436 KB Output is correct
10 Correct 23 ms 47424 KB Output is correct
11 Correct 23 ms 47492 KB Output is correct
12 Correct 23 ms 47488 KB Output is correct
13 Correct 23 ms 47484 KB Output is correct
14 Correct 22 ms 47444 KB Output is correct
15 Correct 23 ms 47596 KB Output is correct
16 Correct 23 ms 47580 KB Output is correct
17 Correct 29 ms 47624 KB Output is correct
18 Correct 26 ms 47640 KB Output is correct
19 Correct 31 ms 47696 KB Output is correct
20 Correct 25 ms 47616 KB Output is correct
21 Correct 26 ms 47700 KB Output is correct
22 Correct 28 ms 48204 KB Output is correct
23 Correct 24 ms 47680 KB Output is correct
24 Correct 26 ms 47676 KB Output is correct
25 Correct 26 ms 47700 KB Output is correct
26 Correct 24 ms 47460 KB Output is correct
27 Correct 31 ms 47424 KB Output is correct
28 Correct 24 ms 47444 KB Output is correct
29 Correct 24 ms 47416 KB Output is correct
30 Correct 2462 ms 533564 KB Output is correct
31 Correct 2421 ms 533588 KB Output is correct
32 Correct 2438 ms 533556 KB Output is correct
33 Correct 2406 ms 533560 KB Output is correct
34 Correct 2430 ms 533504 KB Output is correct
35 Correct 104 ms 71576 KB Output is correct
36 Correct 24 ms 47684 KB Output is correct
37 Correct 23 ms 47432 KB Output is correct
38 Correct 3264 ms 545452 KB Output is correct
39 Correct 115 ms 71756 KB Output is correct
40 Correct 125 ms 70996 KB Output is correct
41 Correct 118 ms 71036 KB Output is correct
42 Correct 116 ms 71664 KB Output is correct
43 Correct 129 ms 71584 KB Output is correct
44 Correct 498 ms 88744 KB Output is correct
45 Correct 113 ms 71580 KB Output is correct
46 Correct 107 ms 71632 KB Output is correct
47 Correct 127 ms 71852 KB Output is correct
48 Correct 693 ms 99660 KB Output is correct
49 Correct 123 ms 70128 KB Output is correct
50 Correct 122 ms 71468 KB Output is correct
51 Correct 132 ms 71032 KB Output is correct
52 Correct 143 ms 70672 KB Output is correct
53 Correct 3532 ms 516744 KB Output is correct
54 Correct 3133 ms 516816 KB Output is correct
55 Correct 3220 ms 533136 KB Output is correct
56 Correct 3168 ms 533052 KB Output is correct
57 Correct 2413 ms 533656 KB Output is correct
58 Correct 2505 ms 533676 KB Output is correct
59 Correct 2586 ms 533716 KB Output is correct
60 Correct 3545 ms 537880 KB Output is correct
61 Correct 3519 ms 495796 KB Output is correct
62 Correct 3631 ms 528460 KB Output is correct
63 Correct 3457 ms 518288 KB Output is correct
64 Correct 3401 ms 507568 KB Output is correct