oj.uz

Submission #721067

# Submission time Handle Problem Language Result Execution time Memory
721067 2023-04-10T09:29:14 Z Rafi22 Event Hopping (BOI22_events) C++14
100 / 100
 459 ms 49528 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=100007,L=17,pot=1<<18;

int l[N],r[N];
int skok[N][L];
map<int,int>M;

pair<int,int>seg[2*pot+7];

void ins(int v,int x,int i)
{
    v+=pot-1;
    seg[v]=min(seg[v],{x,i});
    while(v>1)
    {
        v/=2;
        seg[v]=min(seg[2*v],seg[2*v+1]);
    }
}
pair<int,int>que(int v,int a,int b,int l,int r)
{
    if(a<=l&&b>=r) return seg[v];
    if(r<a||l>b) return {inf,0};
    return min(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    set<int>S;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
        S.insert(l[i]);
        S.insert(r[i]);
    }
    int it=0;
    for(auto x:S) M[x]=++it;
    for(int i=1;i<=n;i++)
    {
        l[i]=M[l[i]];
        r[i]=M[r[i]];
    }
    for(int i=1;i<2*pot;i++) seg[i].st=inf;
    for(int i=1;i<=n;i++) ins(r[i],l[i],i);
    for(int i=1;i<=n;i++) skok[i][0]=que(1,l[i],r[i],1,pot).nd;
    for(int j=1;j<L;j++) for(int i=1;i<=n;i++) skok[i][j]=skok[skok[i][j-1]][j-1];
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        int ans=0;
        for(int i=L-1;i>=0;i--)
        {
            if(l[skok[b][i]]>r[a])
            {
                ans+=(1<<i);
                b=skok[b][i];
            }
        }
        if(a==b) cout<<0<<endl;
        else if(r[b]<r[a]) cout<<"impossible"<<endl;
        else if(l[b]<=r[a]) cout<<1<<endl;
        else if(l[skok[b][0]]<=r[a]) cout<<ans+2<<endl;
        else cout<<"impossible"<<endl;
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 232 ms 36788 KB Output is correct
3 Correct 278 ms 38052 KB Output is correct
4 Correct 273 ms 38032 KB Output is correct
5 Correct 239 ms 39152 KB Output is correct
6 Correct 237 ms 40188 KB Output is correct
7 Correct 272 ms 40476 KB Output is correct
8 Correct 294 ms 49528 KB Output is correct
9 Correct 269 ms 49452 KB Output is correct
10 Correct 225 ms 38304 KB Output is correct
11 Correct 286 ms 42752 KB Output is correct
12 Correct 145 ms 37720 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8528 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Correct 5 ms 8796 KB Output is correct
4 Correct 5 ms 8792 KB Output is correct
5 Correct 5 ms 8788 KB Output is correct
6 Correct 10 ms 8788 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 5 ms 8916 KB Output is correct
9 Correct 4 ms 8712 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8528 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Correct 5 ms 8796 KB Output is correct
4 Correct 5 ms 8792 KB Output is correct
5 Correct 5 ms 8788 KB Output is correct
6 Correct 10 ms 8788 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 5 ms 8916 KB Output is correct
9 Correct 4 ms 8712 KB Output is correct
10 Correct 3 ms 8532 KB Output is correct
11 Correct 4 ms 8528 KB Output is correct
12 Correct 5 ms 8796 KB Output is correct
13 Correct 5 ms 8788 KB Output is correct
14 Correct 5 ms 8788 KB Output is correct
15 Correct 5 ms 8796 KB Output is correct
16 Correct 7 ms 8924 KB Output is correct
17 Correct 6 ms 8924 KB Output is correct
18 Correct 6 ms 8588 KB Output is correct
19 Correct 38 ms 11380 KB Output is correct
20 Correct 33 ms 11340 KB Output is correct
21 Correct 40 ms 11548 KB Output is correct
22 Correct 35 ms 11664 KB Output is correct
23 Correct 37 ms 11984 KB Output is correct
24 Correct 34 ms 11980 KB Output is correct
25 Correct 33 ms 11684 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8528 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Correct 5 ms 8796 KB Output is correct
4 Correct 5 ms 8792 KB Output is correct
5 Correct 5 ms 8788 KB Output is correct
6 Correct 10 ms 8788 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 5 ms 8916 KB Output is correct
9 Correct 4 ms 8712 KB Output is correct
10 Correct 4 ms 8532 KB Output is correct
11 Correct 4 ms 8496 KB Output is correct
12 Correct 5 ms 8792 KB Output is correct
13 Correct 5 ms 8732 KB Output is correct
14 Correct 5 ms 8796 KB Output is correct
15 Correct 5 ms 8720 KB Output is correct
16 Correct 5 ms 8880 KB Output is correct
17 Correct 5 ms 8928 KB Output is correct
18 Correct 5 ms 8660 KB Output is correct
19 Correct 181 ms 36176 KB Output is correct
20 Correct 214 ms 35388 KB Output is correct
21 Correct 202 ms 36216 KB Output is correct
22 Correct 208 ms 40268 KB Output is correct
23 Correct 340 ms 47240 KB Output is correct
24 Correct 349 ms 47236 KB Output is correct
25 Correct 58 ms 24652 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 36848 KB Output is correct
2 Correct 239 ms 37980 KB Output is correct
3 Correct 250 ms 38036 KB Output is correct
4 Correct 310 ms 49440 KB Output is correct
5 Correct 262 ms 38296 KB Output is correct
6 Correct 367 ms 49148 KB Output is correct
7 Correct 459 ms 49220 KB Output is correct
8 Correct 388 ms 49360 KB Output is correct
9 Correct 333 ms 47300 KB Output is correct
10 Correct 355 ms 48748 KB Output is correct
11 Correct 331 ms 48588 KB Output is correct
12 Correct 396 ms 48744 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 232 ms 36788 KB Output is correct
3 Correct 278 ms 38052 KB Output is correct
4 Correct 273 ms 38032 KB Output is correct
5 Correct 239 ms 39152 KB Output is correct
6 Correct 237 ms 40188 KB Output is correct
7 Correct 272 ms 40476 KB Output is correct
8 Correct 294 ms 49528 KB Output is correct
9 Correct 269 ms 49452 KB Output is correct
10 Correct 225 ms 38304 KB Output is correct
11 Correct 286 ms 42752 KB Output is correct
12 Correct 145 ms 37720 KB Output is correct
13 Correct 4 ms 8528 KB Output is correct
14 Correct 5 ms 8532 KB Output is correct
15 Correct 5 ms 8796 KB Output is correct
16 Correct 5 ms 8792 KB Output is correct
17 Correct 5 ms 8788 KB Output is correct
18 Correct 10 ms 8788 KB Output is correct
19 Correct 5 ms 8916 KB Output is correct
20 Correct 5 ms 8916 KB Output is correct
21 Correct 4 ms 8712 KB Output is correct
22 Correct 3 ms 8532 KB Output is correct
23 Correct 4 ms 8528 KB Output is correct
24 Correct 5 ms 8796 KB Output is correct
25 Correct 5 ms 8788 KB Output is correct
26 Correct 5 ms 8788 KB Output is correct
27 Correct 5 ms 8796 KB Output is correct
28 Correct 7 ms 8924 KB Output is correct
29 Correct 6 ms 8924 KB Output is correct
30 Correct 6 ms 8588 KB Output is correct
31 Correct 38 ms 11380 KB Output is correct
32 Correct 33 ms 11340 KB Output is correct
33 Correct 40 ms 11548 KB Output is correct
34 Correct 35 ms 11664 KB Output is correct
35 Correct 37 ms 11984 KB Output is correct
36 Correct 34 ms 11980 KB Output is correct
37 Correct 33 ms 11684 KB Output is correct
38 Correct 4 ms 8532 KB Output is correct
39 Correct 4 ms 8496 KB Output is correct
40 Correct 5 ms 8792 KB Output is correct
41 Correct 5 ms 8732 KB Output is correct
42 Correct 5 ms 8796 KB Output is correct
43 Correct 5 ms 8720 KB Output is correct
44 Correct 5 ms 8880 KB Output is correct
45 Correct 5 ms 8928 KB Output is correct
46 Correct 5 ms 8660 KB Output is correct
47 Correct 181 ms 36176 KB Output is correct
48 Correct 214 ms 35388 KB Output is correct
49 Correct 202 ms 36216 KB Output is correct
50 Correct 208 ms 40268 KB Output is correct
51 Correct 340 ms 47240 KB Output is correct
52 Correct 349 ms 47236 KB Output is correct
53 Correct 58 ms 24652 KB Output is correct
54 Correct 209 ms 36848 KB Output is correct
55 Correct 239 ms 37980 KB Output is correct
56 Correct 250 ms 38036 KB Output is correct
57 Correct 310 ms 49440 KB Output is correct
58 Correct 262 ms 38296 KB Output is correct
59 Correct 367 ms 49148 KB Output is correct
60 Correct 459 ms 49220 KB Output is correct
61 Correct 388 ms 49360 KB Output is correct
62 Correct 333 ms 47300 KB Output is correct
63 Correct 355 ms 48748 KB Output is correct
64 Correct 331 ms 48588 KB Output is correct
65 Correct 396 ms 48744 KB Output is correct
66 Correct 4 ms 8440 KB Output is correct
67 Correct 196 ms 38092 KB Output is correct
68 Correct 238 ms 38036 KB Output is correct
69 Correct 278 ms 37996 KB Output is correct
70 Correct 247 ms 39116 KB Output is correct
71 Correct 242 ms 40108 KB Output is correct
72 Correct 248 ms 40484 KB Output is correct
73 Correct 336 ms 49396 KB Output is correct
74 Correct 268 ms 49484 KB Output is correct
75 Correct 260 ms 38380 KB Output is correct
76 Correct 283 ms 42852 KB Output is correct
77 Correct 150 ms 37732 KB Output is correct
78 Correct 4 ms 8532 KB Output is correct
79 Correct 6 ms 8788 KB Output is correct
80 Correct 5 ms 8788 KB Output is correct
81 Correct 4 ms 8788 KB Output is correct
82 Correct 6 ms 8788 KB Output is correct
83 Correct 6 ms 8916 KB Output is correct
84 Correct 6 ms 8916 KB Output is correct
85 Correct 4 ms 8660 KB Output is correct
86 Correct 37 ms 11484 KB Output is correct
87 Correct 45 ms 11340 KB Output is correct
88 Correct 40 ms 11556 KB Output is correct
89 Correct 38 ms 11596 KB Output is correct
90 Correct 39 ms 11980 KB Output is correct
91 Correct 39 ms 12024 KB Output is correct
92 Correct 37 ms 11672 KB Output is correct
93 Correct 182 ms 36188 KB Output is correct
94 Correct 190 ms 35472 KB Output is correct
95 Correct 199 ms 36196 KB Output is correct
96 Correct 239 ms 40356 KB Output is correct
97 Correct 352 ms 47232 KB Output is correct
98 Correct 342 ms 47132 KB Output is correct
99 Correct 58 ms 24652 KB Output is correct
100 Correct 372 ms 49072 KB Output is correct
101 Correct 377 ms 49060 KB Output is correct
102 Correct 400 ms 49228 KB Output is correct
103 Correct 364 ms 48680 KB Output is correct
104 Correct 370 ms 48524 KB Output is correct
105 Correct 362 ms 48708 KB Output is correct
106 Correct 251 ms 34736 KB Output is correct
107 Correct 296 ms 37372 KB Output is correct
108 Correct 266 ms 38164 KB Output is correct
109 Correct 240 ms 38184 KB Output is correct
110 Correct 445 ms 48992 KB Output is correct
111 Correct 426 ms 49000 KB Output is correct