답안 #660293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660293	2022-11-21T13:30:04 Z	ktkerem	Event Hopping (BOI22_events)	C++17	100 / 100	240 ms	56848 KB

events

/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
/**/
//typedef int ll;
typedef long long ll;
typedef unsigned long long ull;
typedef std::string str;
/*typedef __int128 vll;
typedef unsigned __int128 uvll;*/
#define llll std::pair<ll , ll>
#define pb push_back
#define pf push_front
#define halo cout << "hello\n"
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
const ll limit = 1e14 + 7; 
const ll ous = 1e5 + 7;
const ll dx[4] = {-1 , 0 , 1 , 0} , dy[4] = {0,1,0,-1};
ll n , m;std::vector<llll> ar;
llll rmq[ous][20];ll nex[ous][20];
void solve(){
    for(ll i =0;19>i;i++){
        for(ll j= 0;ous>j;j++){
            rmq[j][i] = {limit , -1};
        }
    }
    memset(nex , 0ll , sizeof(nex));
    ll n , q;std::cin >> n >> q;
    ar.resize(n);
    std::set<ll> st;
    std::vector<ll> b;
    for(ll i = 0;n>i;i++){
        std::cin >> ar[i].fi >> ar[i].sec;
        st.insert(ar[i].sec);
    }
    for(auto j:st){
        b.pb(j);
    }
    for(ll i = 0;n>i;i++){
        ll l = std::lower_bound(all(b) , ar[i].sec) - b.begin();
        rmq[l][0] = std::min(rmq[l][0] , {ar[i].fi , i}); 
    }
    for(ll i = 1;20>i;i++){
        ll o = (1ll << i);
        for(ll j = 0;n >= j + o;j++){
            rmq[j][i] = std::min(rmq[j][i-1] , rmq[j + (1ll << (i-1))][i-1]);
        }
    }
    for(ll i = 0;n>i;i++){
        ll l = std::lower_bound(all(b) , ar[i].fi) - b.begin();
        ll r = std::lower_bound(all(b) , ar[i].sec) - b.begin();
        ll o = log2(r - l + 1);
        llll t = std::min(rmq[l][o] , rmq[r - (1ll << o) + 1][o]);
        nex[i][0] = t.sec;
    }
    for(ll i = 1;20>i;i++){
        for(ll j = 0;n>j;j++){
            nex[j][i] = nex[nex[j][i-1]][i-1];
        }
    }
    //std::cout << nex[7][0] << std::endl;
    while(q--){
        ll x , y;std::cin >> x >> y;x--;y--;
        if(x == y || (ar[x].sec >= ar[y].fi && ar[x].sec <= ar[y].sec)){
            if(x == y){
                std::cout << "0\n";
            }
            else{
                std::cout << "1\n";
            }
            continue;
        }
        ll sc = 1;
        for(ll i = 19;0<=i;i--){
            if(ar[nex[y][i]].fi > ar[x].sec){
                y = nex[y][i];
                sc+= 1ll << i;
                //std::cout << y << std::endl;
            }
        }
        //std::cout << "//" << std::endl;
        y = nex[y][0];
        if(ar[x].sec < ar[y].fi || ar[x].sec > ar[y].sec){
            std::cout << "impossible\n";
        }
        else{
            std::cout << sc + (ar[x].sec >= ar[y].fi) << "\n";
        }
    }
    return;/**/
}
signed main(){
    std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
    ll t=1;
    //std::cin >> t;
    ll o = 1;
    while(t--){ 
        //cout << "Case " << o++ << ":\n";
        solve();
    }
    return 0;
}/**/

Compilation message

events.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |                                                                               
events.cpp: In function 'int main()':
events.cpp:101:8: warning: unused variable 'o' [-Wunused-variable]
  101 |     ll o = 1;
      |        ^

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	47180 KB	Output is correct
2	Correct	170 ms	54960 KB	Output is correct
3	Correct	186 ms	54992 KB	Output is correct
4	Correct	217 ms	54936 KB	Output is correct
5	Correct	192 ms	56408 KB	Output is correct
6	Correct	189 ms	56384 KB	Output is correct
7	Correct	199 ms	56416 KB	Output is correct
8	Correct	167 ms	56772 KB	Output is correct
9	Correct	168 ms	56796 KB	Output is correct
10	Correct	200 ms	56608 KB	Output is correct
11	Correct	193 ms	56696 KB	Output is correct
12	Correct	141 ms	54000 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	47188 KB	Output is correct
2	Correct	28 ms	47256 KB	Output is correct
3	Correct	29 ms	47308 KB	Output is correct
4	Correct	29 ms	47308 KB	Output is correct
5	Correct	31 ms	47312 KB	Output is correct
6	Correct	36 ms	47220 KB	Output is correct
7	Correct	33 ms	47376 KB	Output is correct
8	Correct	29 ms	47380 KB	Output is correct
9	Correct	34 ms	47256 KB	Output is correct

Subtask #3

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	47188 KB	Output is correct
2	Correct	28 ms	47256 KB	Output is correct
3	Correct	29 ms	47308 KB	Output is correct
4	Correct	29 ms	47308 KB	Output is correct
5	Correct	31 ms	47312 KB	Output is correct
6	Correct	36 ms	47220 KB	Output is correct
7	Correct	33 ms	47376 KB	Output is correct
8	Correct	29 ms	47380 KB	Output is correct
9	Correct	34 ms	47256 KB	Output is correct
10	Correct	38 ms	47240 KB	Output is correct
11	Correct	37 ms	47180 KB	Output is correct
12	Correct	30 ms	47364 KB	Output is correct
13	Correct	30 ms	47372 KB	Output is correct
14	Correct	29 ms	47316 KB	Output is correct
15	Correct	29 ms	47316 KB	Output is correct
16	Correct	36 ms	47376 KB	Output is correct
17	Correct	30 ms	47276 KB	Output is correct
18	Correct	29 ms	47236 KB	Output is correct
19	Correct	71 ms	49140 KB	Output is correct
20	Correct	58 ms	49160 KB	Output is correct
21	Correct	63 ms	49424 KB	Output is correct
22	Correct	53 ms	49328 KB	Output is correct
23	Correct	54 ms	49292 KB	Output is correct
24	Correct	51 ms	49356 KB	Output is correct
25	Correct	56 ms	49024 KB	Output is correct

Subtask #4

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	47188 KB	Output is correct
2	Correct	28 ms	47256 KB	Output is correct
3	Correct	29 ms	47308 KB	Output is correct
4	Correct	29 ms	47308 KB	Output is correct
5	Correct	31 ms	47312 KB	Output is correct
6	Correct	36 ms	47220 KB	Output is correct
7	Correct	33 ms	47376 KB	Output is correct
8	Correct	29 ms	47380 KB	Output is correct
9	Correct	34 ms	47256 KB	Output is correct
10	Correct	29 ms	47256 KB	Output is correct
11	Correct	30 ms	47192 KB	Output is correct
12	Correct	33 ms	47308 KB	Output is correct
13	Correct	30 ms	47376 KB	Output is correct
14	Correct	29 ms	47288 KB	Output is correct
15	Correct	32 ms	47320 KB	Output is correct
16	Correct	30 ms	47296 KB	Output is correct
17	Correct	30 ms	47376 KB	Output is correct
18	Correct	29 ms	47296 KB	Output is correct
19	Correct	146 ms	55876 KB	Output is correct
20	Correct	141 ms	55856 KB	Output is correct
21	Correct	140 ms	53068 KB	Output is correct
22	Correct	155 ms	55876 KB	Output is correct
23	Correct	156 ms	55892 KB	Output is correct
24	Correct	149 ms	55944 KB	Output is correct
25	Correct	83 ms	50100 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	171 ms	55036 KB	Output is correct
2	Correct	192 ms	54984 KB	Output is correct
3	Correct	214 ms	54932 KB	Output is correct
4	Correct	181 ms	56836 KB	Output is correct
5	Correct	210 ms	56612 KB	Output is correct
6	Correct	229 ms	56564 KB	Output is correct
7	Correct	238 ms	56408 KB	Output is correct
8	Correct	185 ms	56576 KB	Output is correct
9	Correct	158 ms	55964 KB	Output is correct
10	Correct	191 ms	56100 KB	Output is correct
11	Correct	177 ms	55824 KB	Output is correct
12	Correct	195 ms	56124 KB	Output is correct

Subtask #6

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	47180 KB	Output is correct
2	Correct	170 ms	54960 KB	Output is correct
3	Correct	186 ms	54992 KB	Output is correct
4	Correct	217 ms	54936 KB	Output is correct
5	Correct	192 ms	56408 KB	Output is correct
6	Correct	189 ms	56384 KB	Output is correct
7	Correct	199 ms	56416 KB	Output is correct
8	Correct	167 ms	56772 KB	Output is correct
9	Correct	168 ms	56796 KB	Output is correct
10	Correct	200 ms	56608 KB	Output is correct
11	Correct	193 ms	56696 KB	Output is correct
12	Correct	141 ms	54000 KB	Output is correct
13	Correct	27 ms	47188 KB	Output is correct
14	Correct	28 ms	47256 KB	Output is correct
15	Correct	29 ms	47308 KB	Output is correct
16	Correct	29 ms	47308 KB	Output is correct
17	Correct	31 ms	47312 KB	Output is correct
18	Correct	36 ms	47220 KB	Output is correct
19	Correct	33 ms	47376 KB	Output is correct
20	Correct	29 ms	47380 KB	Output is correct
21	Correct	34 ms	47256 KB	Output is correct
22	Correct	38 ms	47240 KB	Output is correct
23	Correct	37 ms	47180 KB	Output is correct
24	Correct	30 ms	47364 KB	Output is correct
25	Correct	30 ms	47372 KB	Output is correct
26	Correct	29 ms	47316 KB	Output is correct
27	Correct	29 ms	47316 KB	Output is correct
28	Correct	36 ms	47376 KB	Output is correct
29	Correct	30 ms	47276 KB	Output is correct
30	Correct	29 ms	47236 KB	Output is correct
31	Correct	71 ms	49140 KB	Output is correct
32	Correct	58 ms	49160 KB	Output is correct
33	Correct	63 ms	49424 KB	Output is correct
34	Correct	53 ms	49328 KB	Output is correct
35	Correct	54 ms	49292 KB	Output is correct
36	Correct	51 ms	49356 KB	Output is correct
37	Correct	56 ms	49024 KB	Output is correct
38	Correct	29 ms	47256 KB	Output is correct
39	Correct	30 ms	47192 KB	Output is correct
40	Correct	33 ms	47308 KB	Output is correct
41	Correct	30 ms	47376 KB	Output is correct
42	Correct	29 ms	47288 KB	Output is correct
43	Correct	32 ms	47320 KB	Output is correct
44	Correct	30 ms	47296 KB	Output is correct
45	Correct	30 ms	47376 KB	Output is correct
46	Correct	29 ms	47296 KB	Output is correct
47	Correct	146 ms	55876 KB	Output is correct
48	Correct	141 ms	55856 KB	Output is correct
49	Correct	140 ms	53068 KB	Output is correct
50	Correct	155 ms	55876 KB	Output is correct
51	Correct	156 ms	55892 KB	Output is correct
52	Correct	149 ms	55944 KB	Output is correct
53	Correct	83 ms	50100 KB	Output is correct
54	Correct	171 ms	55036 KB	Output is correct
55	Correct	192 ms	54984 KB	Output is correct
56	Correct	214 ms	54932 KB	Output is correct
57	Correct	181 ms	56836 KB	Output is correct
58	Correct	210 ms	56612 KB	Output is correct
59	Correct	229 ms	56564 KB	Output is correct
60	Correct	238 ms	56408 KB	Output is correct
61	Correct	185 ms	56576 KB	Output is correct
62	Correct	158 ms	55964 KB	Output is correct
63	Correct	191 ms	56100 KB	Output is correct
64	Correct	177 ms	55824 KB	Output is correct
65	Correct	195 ms	56124 KB	Output is correct
66	Correct	28 ms	47308 KB	Output is correct
67	Correct	184 ms	56304 KB	Output is correct
68	Correct	192 ms	56348 KB	Output is correct
69	Correct	240 ms	56328 KB	Output is correct
70	Correct	192 ms	56476 KB	Output is correct
71	Correct	186 ms	56324 KB	Output is correct
72	Correct	200 ms	56384 KB	Output is correct
73	Correct	191 ms	56832 KB	Output is correct
74	Correct	176 ms	56848 KB	Output is correct
75	Correct	208 ms	56668 KB	Output is correct
76	Correct	191 ms	56724 KB	Output is correct
77	Correct	128 ms	54056 KB	Output is correct
78	Correct	29 ms	47256 KB	Output is correct
79	Correct	33 ms	47284 KB	Output is correct
80	Correct	29 ms	47284 KB	Output is correct
81	Correct	31 ms	47300 KB	Output is correct
82	Correct	30 ms	47256 KB	Output is correct
83	Correct	30 ms	47292 KB	Output is correct
84	Correct	30 ms	47276 KB	Output is correct
85	Correct	30 ms	47244 KB	Output is correct
86	Correct	58 ms	49156 KB	Output is correct
87	Correct	61 ms	49176 KB	Output is correct
88	Correct	65 ms	49356 KB	Output is correct
89	Correct	54 ms	49344 KB	Output is correct
90	Correct	54 ms	49356 KB	Output is correct
91	Correct	61 ms	49340 KB	Output is correct
92	Correct	55 ms	49072 KB	Output is correct
93	Correct	161 ms	55940 KB	Output is correct
94	Correct	140 ms	55856 KB	Output is correct
95	Correct	142 ms	53060 KB	Output is correct
96	Correct	156 ms	55964 KB	Output is correct
97	Correct	147 ms	55948 KB	Output is correct
98	Correct	148 ms	55920 KB	Output is correct
99	Correct	83 ms	49996 KB	Output is correct
100	Correct	220 ms	56476 KB	Output is correct
101	Correct	219 ms	56576 KB	Output is correct
102	Correct	207 ms	56596 KB	Output is correct
103	Correct	183 ms	56128 KB	Output is correct
104	Correct	180 ms	55876 KB	Output is correct
105	Correct	206 ms	56072 KB	Output is correct
106	Correct	185 ms	55092 KB	Output is correct
107	Correct	229 ms	56528 KB	Output is correct
108	Correct	171 ms	53780 KB	Output is correct
109	Correct	164 ms	53804 KB	Output is correct
110	Correct	191 ms	56312 KB	Output is correct
111	Correct	186 ms	56300 KB	Output is correct