oj.uz

Submission #699436

# Submission time Handle Problem Language Result Execution time Memory
699436 2023-02-16T23:54:12 Z aelf2k23 초음속철도 (OJUZ11_rail) C++14
0 / 100
 3000 ms 14600 KB 
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 200005;

const int mod = 1e9 + 7;

int n, m, dp[nmax];
pair<int,int> a[nmax];

vector<int>vecc;

int32_t main(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> a[i].fr >> a[i].sc;
        swap(a[i].fr, a[i].sc);
        vecc.push_back(a[i].fr);
        vecc.push_back(a[i].sc);
    }
    sort(all(vecc));
    vecc.resize(unique(all(vecc)) - vecc.begin());

    for(int i=1;i<=m;i++){
        a[i].fr = lower_bound(all(vecc), a[i].fr) - vecc.begin();
        a[i].sc = lower_bound(all(vecc), a[i].sc) - vecc.begin();
    }

    sort(a + 1, a + m + 1);
    for(int i=1;i<=m;i++){
        swap(a[i].fr, a[i].sc);
    }

    for(int i=1;i<=m;i++){
        cout << a[i].fr << ' ' << a[i].sc << '\n';
    }

    int n = vecc.size() - 1;

    dp[0] = 1;

    for(int i=1;i<=m;i++){
        for(int j=0;j<a[i].fr;j++){
            dp[j] = dp[j] * 2LL % mod;
        }
        for(int j=a[i].sc;j>=a[i].fr;j--){
            dp[a[i].sc] += dp[j];
        }
    }
    

    cout << dp[n] << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Incorrect 1 ms 308 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Incorrect 1 ms 304 KB Output isn't correct
12 Incorrect 0 ms 308 KB Output isn't correct
13 Incorrect 0 ms 212 KB Output isn't correct
14 Incorrect 0 ms 212 KB Output isn't correct
15 Incorrect 0 ms 212 KB Output isn't correct
16 Incorrect 0 ms 212 KB Output isn't correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Incorrect 0 ms 212 KB Output isn't correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Incorrect 1 ms 308 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Incorrect 1 ms 304 KB Output isn't correct
12 Incorrect 0 ms 308 KB Output isn't correct
13 Incorrect 0 ms 212 KB Output isn't correct
14 Incorrect 0 ms 212 KB Output isn't correct
15 Incorrect 0 ms 212 KB Output isn't correct
16 Incorrect 0 ms 212 KB Output isn't correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Incorrect 0 ms 212 KB Output isn't correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Incorrect 1 ms 212 KB Output isn't correct
23 Incorrect 0 ms 312 KB Output isn't correct
24 Incorrect 1 ms 212 KB Output isn't correct
25 Incorrect 1 ms 212 KB Output isn't correct
26 Incorrect 0 ms 212 KB Output isn't correct
27 Incorrect 1 ms 212 KB Output isn't correct
28 Incorrect 1 ms 212 KB Output isn't correct
29 Incorrect 1 ms 212 KB Output isn't correct
30 Incorrect 1 ms 312 KB Output isn't correct
31 Incorrect 0 ms 212 KB Output isn't correct
32 Incorrect 0 ms 212 KB Output isn't correct
33 Incorrect 1 ms 340 KB Output isn't correct
34 Incorrect 0 ms 212 KB Output isn't correct
35 Incorrect 0 ms 316 KB Output isn't correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 312 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Incorrect 11 ms 724 KB Output isn't correct
5 Execution timed out 3081 ms 13560 KB Time limit exceeded
6 Execution timed out 3066 ms 13900 KB Time limit exceeded
7 Execution timed out 3089 ms 12680 KB Time limit exceeded
8 Incorrect 1 ms 308 KB Output isn't correct
9 Execution timed out 3065 ms 12904 KB Time limit exceeded
10 Execution timed out 3065 ms 13724 KB Time limit exceeded
11 Incorrect 2483 ms 7132 KB Output isn't correct
12 Execution timed out 3070 ms 13956 KB Time limit exceeded
13 Execution timed out 3042 ms 13908 KB Time limit exceeded
14 Incorrect 147 ms 9992 KB Output isn't correct
15 Execution timed out 3057 ms 13900 KB Time limit exceeded
16 Incorrect 164 ms 10640 KB Output isn't correct
17 Execution timed out 3050 ms 14080 KB Time limit exceeded
18 Execution timed out 3051 ms 14188 KB Time limit exceeded
19 Execution timed out 3068 ms 14104 KB Time limit exceeded

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Incorrect 1 ms 308 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Incorrect 1 ms 304 KB Output isn't correct
12 Incorrect 0 ms 308 KB Output isn't correct
13 Incorrect 0 ms 212 KB Output isn't correct
14 Incorrect 0 ms 212 KB Output isn't correct
15 Incorrect 0 ms 212 KB Output isn't correct
16 Incorrect 0 ms 212 KB Output isn't correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Incorrect 0 ms 212 KB Output isn't correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Incorrect 1 ms 212 KB Output isn't correct
23 Incorrect 0 ms 312 KB Output isn't correct
24 Incorrect 1 ms 212 KB Output isn't correct
25 Incorrect 1 ms 212 KB Output isn't correct
26 Incorrect 0 ms 212 KB Output isn't correct
27 Incorrect 1 ms 212 KB Output isn't correct
28 Incorrect 1 ms 212 KB Output isn't correct
29 Incorrect 1 ms 212 KB Output isn't correct
30 Incorrect 1 ms 312 KB Output isn't correct
31 Incorrect 0 ms 212 KB Output isn't correct
32 Incorrect 0 ms 212 KB Output isn't correct
33 Incorrect 1 ms 340 KB Output isn't correct
34 Incorrect 0 ms 212 KB Output isn't correct
35 Incorrect 0 ms 316 KB Output isn't correct
36 Incorrect 39 ms 728 KB Output isn't correct
37 Incorrect 27 ms 768 KB Output isn't correct
38 Incorrect 12 ms 648 KB Output isn't correct
39 Incorrect 3 ms 596 KB Output isn't correct
40 Incorrect 24 ms 776 KB Output isn't correct
41 Incorrect 39 ms 792 KB Output isn't correct
42 Incorrect 39 ms 724 KB Output isn't correct
43 Incorrect 1 ms 212 KB Output isn't correct
44 Incorrect 19 ms 728 KB Output isn't correct
45 Incorrect 4 ms 580 KB Output isn't correct
46 Incorrect 24 ms 764 KB Output isn't correct
47 Incorrect 24 ms 792 KB Output isn't correct
48 Incorrect 24 ms 724 KB Output isn't correct
49 Incorrect 5 ms 708 KB Output isn't correct
50 Incorrect 6 ms 644 KB Output isn't correct
51 Incorrect 6 ms 704 KB Output isn't correct
52 Incorrect 3 ms 340 KB Output isn't correct
53 Incorrect 40 ms 724 KB Output isn't correct
54 Incorrect 10 ms 588 KB Output isn't correct
55 Incorrect 38 ms 808 KB Output isn't correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Incorrect 1 ms 308 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Incorrect 1 ms 304 KB Output isn't correct
12 Incorrect 0 ms 308 KB Output isn't correct
13 Incorrect 0 ms 212 KB Output isn't correct
14 Incorrect 0 ms 212 KB Output isn't correct
15 Incorrect 0 ms 212 KB Output isn't correct
16 Incorrect 0 ms 212 KB Output isn't correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Incorrect 0 ms 212 KB Output isn't correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Incorrect 1 ms 212 KB Output isn't correct
23 Incorrect 0 ms 312 KB Output isn't correct
24 Incorrect 1 ms 212 KB Output isn't correct
25 Incorrect 1 ms 212 KB Output isn't correct
26 Incorrect 0 ms 212 KB Output isn't correct
27 Incorrect 1 ms 212 KB Output isn't correct
28 Incorrect 1 ms 212 KB Output isn't correct
29 Incorrect 1 ms 212 KB Output isn't correct
30 Incorrect 1 ms 312 KB Output isn't correct
31 Incorrect 0 ms 212 KB Output isn't correct
32 Incorrect 0 ms 212 KB Output isn't correct
33 Incorrect 1 ms 340 KB Output isn't correct
34 Incorrect 0 ms 212 KB Output isn't correct
35 Incorrect 0 ms 316 KB Output isn't correct
36 Incorrect 0 ms 312 KB Output isn't correct
37 Incorrect 1 ms 212 KB Output isn't correct
38 Incorrect 0 ms 212 KB Output isn't correct
39 Incorrect 11 ms 724 KB Output isn't correct
40 Execution timed out 3081 ms 13560 KB Time limit exceeded
41 Execution timed out 3066 ms 13900 KB Time limit exceeded
42 Execution timed out 3089 ms 12680 KB Time limit exceeded
43 Incorrect 1 ms 308 KB Output isn't correct
44 Execution timed out 3065 ms 12904 KB Time limit exceeded
45 Execution timed out 3065 ms 13724 KB Time limit exceeded
46 Incorrect 2483 ms 7132 KB Output isn't correct
47 Execution timed out 3070 ms 13956 KB Time limit exceeded
48 Execution timed out 3042 ms 13908 KB Time limit exceeded
49 Incorrect 147 ms 9992 KB Output isn't correct
50 Execution timed out 3057 ms 13900 KB Time limit exceeded
51 Incorrect 164 ms 10640 KB Output isn't correct
52 Execution timed out 3050 ms 14080 KB Time limit exceeded
53 Execution timed out 3051 ms 14188 KB Time limit exceeded
54 Execution timed out 3068 ms 14104 KB Time limit exceeded
55 Incorrect 39 ms 728 KB Output isn't correct
56 Incorrect 27 ms 768 KB Output isn't correct
57 Incorrect 12 ms 648 KB Output isn't correct
58 Incorrect 3 ms 596 KB Output isn't correct
59 Incorrect 24 ms 776 KB Output isn't correct
60 Incorrect 39 ms 792 KB Output isn't correct
61 Incorrect 39 ms 724 KB Output isn't correct
62 Incorrect 1 ms 212 KB Output isn't correct
63 Incorrect 19 ms 728 KB Output isn't correct
64 Incorrect 4 ms 580 KB Output isn't correct
65 Incorrect 24 ms 764 KB Output isn't correct
66 Incorrect 24 ms 792 KB Output isn't correct
67 Incorrect 24 ms 724 KB Output isn't correct
68 Incorrect 5 ms 708 KB Output isn't correct
69 Incorrect 6 ms 644 KB Output isn't correct
70 Incorrect 6 ms 704 KB Output isn't correct
71 Incorrect 3 ms 340 KB Output isn't correct
72 Incorrect 40 ms 724 KB Output isn't correct
73 Incorrect 10 ms 588 KB Output isn't correct
74 Incorrect 38 ms 808 KB Output isn't correct
75 Execution timed out 3060 ms 14512 KB Time limit exceeded
76 Execution timed out 3055 ms 10036 KB Time limit exceeded
77 Incorrect 530 ms 9940 KB Output isn't correct
78 Incorrect 98 ms 8256 KB Output isn't correct
79 Execution timed out 3066 ms 12800 KB Time limit exceeded
80 Execution timed out 3060 ms 14596 KB Time limit exceeded
81 Incorrect 19 ms 724 KB Output isn't correct
82 Execution timed out 3055 ms 13736 KB Time limit exceeded
83 Incorrect 138 ms 9984 KB Output isn't correct
84 Execution timed out 3071 ms 13884 KB Time limit exceeded
85 Execution timed out 3054 ms 14000 KB Time limit exceeded
86 Execution timed out 3068 ms 13936 KB Time limit exceeded
87 Incorrect 205 ms 11636 KB Output isn't correct
88 Incorrect 205 ms 11924 KB Output isn't correct
89 Execution timed out 3067 ms 14464 KB Time limit exceeded
90 Execution timed out 3074 ms 14408 KB Time limit exceeded
91 Execution timed out 3076 ms 14556 KB Time limit exceeded
92 Execution timed out 3070 ms 13872 KB Time limit exceeded
93 Execution timed out 3059 ms 14168 KB Time limit exceeded
94 Execution timed out 3063 ms 14600 KB Time limit exceeded
95 Execution timed out 3080 ms 14528 KB Time limit exceeded