답안 #705629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705629	2023-03-04T20:13:46 Z	Username4132	Osumnjičeni (COCI21_osumnjiceni)	C++14	110 / 110	388 ms	42216 KB

Main

#include<iostream>
#include<set>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define F first
#define S second

const int MAXN=200010;
int n, q, l[MAXN], r[MAXN], up[20][MAXN], lo=0;

set<pii> s;

bool test(int ld, int rd){
    auto itrl=s.lower_bound({ld, -2}), itrr=s.upper_bound({rd, 1100000000});
    return (itrl->F==itrr->F) && (itrr==s.end() || itrr->S < n);
}

int main(){
    scanf("%d", &n);
    forn(i, n){
        scanf("%d %d", l+i, r+i);
        while(!test(l[i], r[i])){
            s.erase({l[lo], lo});
            s.erase({r[lo], n+lo});
            up[0][lo++]=i;
        }
        s.insert({l[i], i});
        s.insert({r[i], n+i});
    }
    while(lo<=n) up[0][lo++]=n;
    forn(i, 19) forn(j, n+1) up[i+1][j]=up[i][up[i][j]];
    scanf("%d", &q);
    forn(qnum, q){
        int a, b, ans=1; scanf("%d %d", &a, &b); --a;
        dforn(i, 20) if(up[i][a]<b) a=up[i][a], ans+=(1<<i);
        printf("%d\n", ans);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d %d", l+i, r+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:36:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         int a, b, ans=1; scanf("%d %d", &a, &b); --a;
      |                          ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	20512 KB	Output is correct
2	Correct	81 ms	20220 KB	Output is correct
3	Correct	81 ms	20240 KB	Output is correct
4	Correct	87 ms	20416 KB	Output is correct
5	Correct	90 ms	21288 KB	Output is correct
6	Correct	75 ms	19484 KB	Output is correct
7	Correct	79 ms	19792 KB	Output is correct
8	Correct	85 ms	19908 KB	Output is correct
9	Correct	93 ms	20336 KB	Output is correct
10	Correct	102 ms	19788 KB	Output is correct
11	Correct	240 ms	38696 KB	Output is correct
12	Correct	222 ms	36428 KB	Output is correct
13	Correct	240 ms	36328 KB	Output is correct
14	Correct	274 ms	30920 KB	Output is correct
15	Correct	245 ms	27704 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	81 ms	20736 KB	Output is correct

Subtask #2

10.0 / 10.0

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

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	980 KB	Output is correct
2	Correct	5 ms	980 KB	Output is correct
3	Correct	4 ms	980 KB	Output is correct
4	Correct	4 ms	980 KB	Output is correct
5	Correct	4 ms	980 KB	Output is correct
6	Correct	5 ms	980 KB	Output is correct
7	Correct	4 ms	980 KB	Output is correct
8	Correct	4 ms	980 KB	Output is correct
9	Correct	5 ms	980 KB	Output is correct
10	Correct	5 ms	960 KB	Output is correct
11	Correct	6 ms	1364 KB	Output is correct
12	Correct	6 ms	1364 KB	Output is correct
13	Correct	7 ms	1344 KB	Output is correct
14	Correct	7 ms	1108 KB	Output is correct
15	Correct	7 ms	1080 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	4 ms	980 KB	Output is correct
18	Correct	77 ms	3628 KB	Output is correct
19	Correct	75 ms	3260 KB	Output is correct
20	Correct	87 ms	3652 KB	Output is correct
21	Correct	73 ms	3336 KB	Output is correct
22	Correct	78 ms	3464 KB	Output is correct
23	Correct	72 ms	3352 KB	Output is correct
24	Correct	75 ms	3460 KB	Output is correct
25	Correct	77 ms	3492 KB	Output is correct
26	Correct	73 ms	3508 KB	Output is correct
27	Correct	69 ms	3244 KB	Output is correct
28	Correct	73 ms	3356 KB	Output is correct
29	Correct	75 ms	3468 KB	Output is correct
30	Correct	60 ms	3508 KB	Output is correct
31	Correct	65 ms	3136 KB	Output is correct
32	Correct	60 ms	3316 KB	Output is correct
33	Correct	1 ms	308 KB	Output is correct
34	Correct	59 ms	3228 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	84 ms	21348 KB	Output is correct
2	Correct	85 ms	21020 KB	Output is correct
3	Correct	79 ms	19472 KB	Output is correct
4	Correct	99 ms	19364 KB	Output is correct
5	Correct	84 ms	19896 KB	Output is correct
6	Correct	72 ms	19660 KB	Output is correct
7	Correct	81 ms	19580 KB	Output is correct
8	Correct	83 ms	19492 KB	Output is correct
9	Correct	89 ms	19352 KB	Output is correct
10	Correct	106 ms	20840 KB	Output is correct
11	Correct	257 ms	36080 KB	Output is correct
12	Correct	253 ms	39548 KB	Output is correct
13	Correct	216 ms	36060 KB	Output is correct
14	Correct	274 ms	28100 KB	Output is correct
15	Correct	267 ms	31044 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	87 ms	19936 KB	Output is correct

Subtask #5

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	20512 KB	Output is correct
2	Correct	81 ms	20220 KB	Output is correct
3	Correct	81 ms	20240 KB	Output is correct
4	Correct	87 ms	20416 KB	Output is correct
5	Correct	90 ms	21288 KB	Output is correct
6	Correct	75 ms	19484 KB	Output is correct
7	Correct	79 ms	19792 KB	Output is correct
8	Correct	85 ms	19908 KB	Output is correct
9	Correct	93 ms	20336 KB	Output is correct
10	Correct	102 ms	19788 KB	Output is correct
11	Correct	240 ms	38696 KB	Output is correct
12	Correct	222 ms	36428 KB	Output is correct
13	Correct	240 ms	36328 KB	Output is correct
14	Correct	274 ms	30920 KB	Output is correct
15	Correct	245 ms	27704 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	81 ms	20736 KB	Output is correct
18	Correct	5 ms	980 KB	Output is correct
19	Correct	5 ms	980 KB	Output is correct
20	Correct	4 ms	980 KB	Output is correct
21	Correct	4 ms	980 KB	Output is correct
22	Correct	4 ms	980 KB	Output is correct
23	Correct	5 ms	980 KB	Output is correct
24	Correct	4 ms	980 KB	Output is correct
25	Correct	4 ms	980 KB	Output is correct
26	Correct	5 ms	980 KB	Output is correct
27	Correct	5 ms	960 KB	Output is correct
28	Correct	6 ms	1364 KB	Output is correct
29	Correct	6 ms	1364 KB	Output is correct
30	Correct	7 ms	1344 KB	Output is correct
31	Correct	7 ms	1108 KB	Output is correct
32	Correct	7 ms	1080 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	4 ms	980 KB	Output is correct
35	Correct	77 ms	3628 KB	Output is correct
36	Correct	75 ms	3260 KB	Output is correct
37	Correct	87 ms	3652 KB	Output is correct
38	Correct	73 ms	3336 KB	Output is correct
39	Correct	78 ms	3464 KB	Output is correct
40	Correct	72 ms	3352 KB	Output is correct
41	Correct	75 ms	3460 KB	Output is correct
42	Correct	77 ms	3492 KB	Output is correct
43	Correct	73 ms	3508 KB	Output is correct
44	Correct	69 ms	3244 KB	Output is correct
45	Correct	73 ms	3356 KB	Output is correct
46	Correct	75 ms	3468 KB	Output is correct
47	Correct	60 ms	3508 KB	Output is correct
48	Correct	65 ms	3136 KB	Output is correct
49	Correct	60 ms	3316 KB	Output is correct
50	Correct	1 ms	308 KB	Output is correct
51	Correct	59 ms	3228 KB	Output is correct
52	Correct	84 ms	21348 KB	Output is correct
53	Correct	85 ms	21020 KB	Output is correct
54	Correct	79 ms	19472 KB	Output is correct
55	Correct	99 ms	19364 KB	Output is correct
56	Correct	84 ms	19896 KB	Output is correct
57	Correct	72 ms	19660 KB	Output is correct
58	Correct	81 ms	19580 KB	Output is correct
59	Correct	83 ms	19492 KB	Output is correct
60	Correct	89 ms	19352 KB	Output is correct
61	Correct	106 ms	20840 KB	Output is correct
62	Correct	257 ms	36080 KB	Output is correct
63	Correct	253 ms	39548 KB	Output is correct
64	Correct	216 ms	36060 KB	Output is correct
65	Correct	274 ms	28100 KB	Output is correct
66	Correct	267 ms	31044 KB	Output is correct
67	Correct	1 ms	340 KB	Output is correct
68	Correct	87 ms	19936 KB	Output is correct
69	Correct	321 ms	23480 KB	Output is correct
70	Correct	304 ms	24524 KB	Output is correct
71	Correct	311 ms	22864 KB	Output is correct
72	Correct	296 ms	23880 KB	Output is correct
73	Correct	298 ms	23528 KB	Output is correct
74	Correct	320 ms	24816 KB	Output is correct
75	Correct	293 ms	23224 KB	Output is correct
76	Correct	365 ms	24840 KB	Output is correct
77	Correct	296 ms	23044 KB	Output is correct
78	Correct	295 ms	23400 KB	Output is correct
79	Correct	352 ms	42216 KB	Output is correct
80	Correct	336 ms	39116 KB	Output is correct
81	Correct	330 ms	38904 KB	Output is correct
82	Correct	388 ms	31124 KB	Output is correct
83	Correct	343 ms	30116 KB	Output is correct
84	Correct	1 ms	340 KB	Output is correct
85	Correct	149 ms	23052 KB	Output is correct