답안 #541162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541162	2022-03-22T12:33:02 Z	AlperenT	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	272 ms	33644 KB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5, K = 20, INF = 1e9 + 5;

int n, q, a, b, nxt[N], binlift[N][K];

pair<int, int> arr[N];

multiset<pair<int, int>> st;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n;

    for(int i = 1; i <= n; i++) cin >> arr[i].first >> arr[i].second;

    int r = 0;

    for(int i = 1; i <= n; i++){
        while(r <= n - 1){
            auto it = st.insert(arr[r + 1]);

            if(it != st.begin() && prev(it)->second >= arr[r + 1].first){
                st.erase(st.find(arr[r + 1]));
                break;
            }
            if(next(it) != st.end() && next(it)->first <= arr[r + 1].second){
                st.erase(st.find(arr[r + 1]));
                break;
            } 

            r++;
        }

        nxt[i] = r + 1;

        st.erase(st.find(arr[i]));
    }

    for(int i = n; i >= 1; i--){
        binlift[i][0] = nxt[i];

        for(int j = 1; j < K; j++) binlift[i][j] = binlift[binlift[i][j - 1]][j - 1];
    }

    cin >> q;

    while(q--){
        cin >> a >> b;

        int ans = 0;

        for(int i = K - 1; i >= 0; i--){
            if(binlift[a][i] != 0 && binlift[a][i] <= b){
                ans += 1 << i;
                a = binlift[a][i];
            }
        }

        cout << ans + 1 << "\n";
    }
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	21124 KB	Output is correct
2	Correct	81 ms	20916 KB	Output is correct
3	Correct	80 ms	20840 KB	Output is correct
4	Correct	81 ms	21144 KB	Output is correct
5	Correct	80 ms	22088 KB	Output is correct
6	Correct	71 ms	20144 KB	Output is correct
7	Correct	71 ms	20420 KB	Output is correct
8	Correct	84 ms	20608 KB	Output is correct
9	Correct	86 ms	21028 KB	Output is correct
10	Correct	91 ms	20300 KB	Output is correct
11	Correct	185 ms	30272 KB	Output is correct
12	Correct	191 ms	28584 KB	Output is correct
13	Correct	182 ms	28396 KB	Output is correct
14	Correct	168 ms	26316 KB	Output is correct
15	Correct	154 ms	24544 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	79 ms	21520 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	852 KB	Output is correct
2	Correct	4 ms	852 KB	Output is correct
3	Correct	4 ms	852 KB	Output is correct
4	Correct	4 ms	852 KB	Output is correct
5	Correct	4 ms	852 KB	Output is correct
6	Correct	5 ms	856 KB	Output is correct
7	Correct	4 ms	852 KB	Output is correct
8	Correct	4 ms	828 KB	Output is correct
9	Correct	4 ms	856 KB	Output is correct
10	Correct	4 ms	824 KB	Output is correct
11	Correct	5 ms	1112 KB	Output is correct
12	Correct	4 ms	980 KB	Output is correct
13	Correct	4 ms	980 KB	Output is correct
14	Correct	5 ms	980 KB	Output is correct
15	Correct	4 ms	960 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	4 ms	852 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	852 KB	Output is correct
2	Correct	4 ms	852 KB	Output is correct
3	Correct	4 ms	852 KB	Output is correct
4	Correct	4 ms	852 KB	Output is correct
5	Correct	4 ms	852 KB	Output is correct
6	Correct	5 ms	856 KB	Output is correct
7	Correct	4 ms	852 KB	Output is correct
8	Correct	4 ms	828 KB	Output is correct
9	Correct	4 ms	856 KB	Output is correct
10	Correct	4 ms	824 KB	Output is correct
11	Correct	5 ms	1112 KB	Output is correct
12	Correct	4 ms	980 KB	Output is correct
13	Correct	4 ms	980 KB	Output is correct
14	Correct	5 ms	980 KB	Output is correct
15	Correct	4 ms	960 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	4 ms	852 KB	Output is correct
18	Correct	67 ms	3472 KB	Output is correct
19	Correct	65 ms	3276 KB	Output is correct
20	Correct	74 ms	3596 KB	Output is correct
21	Correct	62 ms	3320 KB	Output is correct
22	Correct	65 ms	3452 KB	Output is correct
23	Correct	62 ms	3324 KB	Output is correct
24	Correct	65 ms	3464 KB	Output is correct
25	Correct	67 ms	3524 KB	Output is correct
26	Correct	63 ms	3396 KB	Output is correct
27	Correct	64 ms	3252 KB	Output is correct
28	Correct	48 ms	3116 KB	Output is correct
29	Correct	53 ms	3296 KB	Output is correct
30	Correct	53 ms	3224 KB	Output is correct
31	Correct	50 ms	3056 KB	Output is correct
32	Correct	51 ms	3172 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	52 ms	3152 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	89 ms	22220 KB	Output is correct
2	Correct	81 ms	21708 KB	Output is correct
3	Correct	74 ms	20192 KB	Output is correct
4	Correct	75 ms	20000 KB	Output is correct
5	Correct	76 ms	20564 KB	Output is correct
6	Correct	72 ms	20264 KB	Output is correct
7	Correct	70 ms	20140 KB	Output is correct
8	Correct	76 ms	20280 KB	Output is correct
9	Correct	76 ms	20116 KB	Output is correct
10	Correct	89 ms	21616 KB	Output is correct
11	Correct	172 ms	28148 KB	Output is correct
12	Correct	198 ms	30868 KB	Output is correct
13	Correct	161 ms	28156 KB	Output is correct
14	Correct	161 ms	24592 KB	Output is correct
15	Correct	168 ms	26600 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	70 ms	20496 KB	Output is correct

Subtask #5
50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	21124 KB	Output is correct
2	Correct	81 ms	20916 KB	Output is correct
3	Correct	80 ms	20840 KB	Output is correct
4	Correct	81 ms	21144 KB	Output is correct
5	Correct	80 ms	22088 KB	Output is correct
6	Correct	71 ms	20144 KB	Output is correct
7	Correct	71 ms	20420 KB	Output is correct
8	Correct	84 ms	20608 KB	Output is correct
9	Correct	86 ms	21028 KB	Output is correct
10	Correct	91 ms	20300 KB	Output is correct
11	Correct	185 ms	30272 KB	Output is correct
12	Correct	191 ms	28584 KB	Output is correct
13	Correct	182 ms	28396 KB	Output is correct
14	Correct	168 ms	26316 KB	Output is correct
15	Correct	154 ms	24544 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	79 ms	21520 KB	Output is correct
18	Correct	5 ms	852 KB	Output is correct
19	Correct	4 ms	852 KB	Output is correct
20	Correct	4 ms	852 KB	Output is correct
21	Correct	4 ms	852 KB	Output is correct
22	Correct	4 ms	852 KB	Output is correct
23	Correct	5 ms	856 KB	Output is correct
24	Correct	4 ms	852 KB	Output is correct
25	Correct	4 ms	828 KB	Output is correct
26	Correct	4 ms	856 KB	Output is correct
27	Correct	4 ms	824 KB	Output is correct
28	Correct	5 ms	1112 KB	Output is correct
29	Correct	4 ms	980 KB	Output is correct
30	Correct	4 ms	980 KB	Output is correct
31	Correct	5 ms	980 KB	Output is correct
32	Correct	4 ms	960 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	4 ms	852 KB	Output is correct
35	Correct	67 ms	3472 KB	Output is correct
36	Correct	65 ms	3276 KB	Output is correct
37	Correct	74 ms	3596 KB	Output is correct
38	Correct	62 ms	3320 KB	Output is correct
39	Correct	65 ms	3452 KB	Output is correct
40	Correct	62 ms	3324 KB	Output is correct
41	Correct	65 ms	3464 KB	Output is correct
42	Correct	67 ms	3524 KB	Output is correct
43	Correct	63 ms	3396 KB	Output is correct
44	Correct	64 ms	3252 KB	Output is correct
45	Correct	48 ms	3116 KB	Output is correct
46	Correct	53 ms	3296 KB	Output is correct
47	Correct	53 ms	3224 KB	Output is correct
48	Correct	50 ms	3056 KB	Output is correct
49	Correct	51 ms	3172 KB	Output is correct
50	Correct	1 ms	340 KB	Output is correct
51	Correct	52 ms	3152 KB	Output is correct
52	Correct	89 ms	22220 KB	Output is correct
53	Correct	81 ms	21708 KB	Output is correct
54	Correct	74 ms	20192 KB	Output is correct
55	Correct	75 ms	20000 KB	Output is correct
56	Correct	76 ms	20564 KB	Output is correct
57	Correct	72 ms	20264 KB	Output is correct
58	Correct	70 ms	20140 KB	Output is correct
59	Correct	76 ms	20280 KB	Output is correct
60	Correct	76 ms	20116 KB	Output is correct
61	Correct	89 ms	21616 KB	Output is correct
62	Correct	172 ms	28148 KB	Output is correct
63	Correct	198 ms	30868 KB	Output is correct
64	Correct	161 ms	28156 KB	Output is correct
65	Correct	161 ms	24592 KB	Output is correct
66	Correct	168 ms	26600 KB	Output is correct
67	Correct	0 ms	340 KB	Output is correct
68	Correct	70 ms	20496 KB	Output is correct
69	Correct	260 ms	24372 KB	Output is correct
70	Correct	253 ms	25192 KB	Output is correct
71	Correct	228 ms	23432 KB	Output is correct
72	Correct	242 ms	24500 KB	Output is correct
73	Correct	241 ms	24248 KB	Output is correct
74	Correct	272 ms	25520 KB	Output is correct
75	Correct	250 ms	23836 KB	Output is correct
76	Correct	270 ms	25672 KB	Output is correct
77	Correct	238 ms	23700 KB	Output is correct
78	Correct	236 ms	24240 KB	Output is correct
79	Correct	263 ms	33644 KB	Output is correct
80	Correct	267 ms	31200 KB	Output is correct
81	Correct	229 ms	30940 KB	Output is correct
82	Correct	214 ms	27740 KB	Output is correct
83	Correct	215 ms	26652 KB	Output is correct
84	Correct	0 ms	340 KB	Output is correct
85	Correct	142 ms	23748 KB	Output is correct

답안 #541162

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 10.0 / 10.0

Subtask #3 20.0 / 20.0

Subtask #4 20.0 / 20.0

Subtask #5 50.0 / 50.0

Subtask #1
10.0 / 10.0

Subtask #2
10.0 / 10.0

Subtask #3
20.0 / 20.0

Subtask #4
20.0 / 20.0

Subtask #5
50.0 / 50.0