oj.uz

Submission #660100

# Submission time Handle Problem Language Result Execution time Memory
660100 2022-11-20T11:04:24 Z Karuk Event Hopping (BOI22_events) C++14
50 / 100
 1500 ms 127952 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
pair<int,int>max(pair<int,int>a,pair<int,int>b) {
    return a>b?a:b;
}
const int k=(1<<30);
unordered_map<int,pair<int,int> >maxv;
void upd(int x,int va,int ind) {
    pair<int,int>val={va,ind};
    while(x>0) {
        maxv[x]=max(maxv[x],val);
        x>>=1;
    }
}
pair<int,int> ask(int from,int to,int cur=1,int beg=0,int en=k-1) {
    if(from<=beg && en<=to)return maxv[cur];
    if(to<beg || en<from)return {-1,-1};
    int mid=(beg+en)/2;
    return max(ask(from,to,cur*2,beg,mid),ask(from,to,cur*2+1,mid+1,en));
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,q;cin>>n>>q;
    pair<int,int>a[n];
    for(int i=0;i<n;i++) {
        int x,y;
        cin>>x>>y;
        a[i]={x,y};
        upd(y+k,k-x,i);
    }
    pair<int,int> prev[n][25];
    for(int i=0;i<n;i++) {
        pair<int,int>d=ask(a[i].first,a[i].second);
        d.first=k-d.first;
        prev[i][0]=d;
    }
    for(int j=1;j<25;j++) {
        for(int i=0;i<n;i++) {
            prev[i][j]=prev[prev[i][j-1].second][j-1];
        }
    }
    for(int i=0;i<q;i++) {
        int x,y;cin>>x>>y;x--;y--;
        if(x==y)cout<<0<<endl;
        else if(a[x].second>=a[y].first && a[x].second<=a[y].second)cout<<1<<endl;
        else if(a[x].second>a[y].second){cout<<"impossible"<<endl;}
        else {
            int cnt=0;
            int cur=y;
            int en=a[x].second;
            for(int j=24;j>=0;j--) {
                if(prev[cur][j].first>en) {
                    cur=prev[cur][j].second;
                    cnt+=(1<<j);
                }
            }
            if(prev[cur][0].first>en)cout<<"impossible"<<endl;
            else cout<<cnt+2<<endl;
        }
    }
    return 0;
}
///9:30

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1218 ms 116356 KB Output is correct
3 Correct 1242 ms 119228 KB Output is correct
4 Correct 1339 ms 120904 KB Output is correct
5 Correct 1264 ms 125088 KB Output is correct
6 Correct 1235 ms 124696 KB Output is correct
7 Correct 1237 ms 121320 KB Output is correct
8 Correct 1118 ms 116056 KB Output is correct
9 Correct 1251 ms 126856 KB Output is correct
10 Correct 1233 ms 118200 KB Output is correct
11 Correct 1187 ms 117308 KB Output is correct
12 Correct 182 ms 34672 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 6 ms 1952 KB Output is correct
4 Correct 6 ms 1968 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct
7 Correct 6 ms 1968 KB Output is correct
8 Correct 8 ms 1968 KB Output is correct
9 Correct 3 ms 468 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 6 ms 1952 KB Output is correct
4 Correct 6 ms 1968 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct
7 Correct 6 ms 1968 KB Output is correct
8 Correct 8 ms 1968 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 5 ms 1968 KB Output is correct
13 Correct 6 ms 1968 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 5 ms 1236 KB Output is correct
16 Correct 7 ms 1968 KB Output is correct
17 Correct 7 ms 1968 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 44 ms 2392 KB Output is correct
20 Correct 71 ms 7884 KB Output is correct
21 Correct 48 ms 2372 KB Output is correct
22 Correct 43 ms 5348 KB Output is correct
23 Correct 53 ms 8640 KB Output is correct
24 Correct 50 ms 8528 KB Output is correct
25 Correct 70 ms 10772 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 6 ms 1952 KB Output is correct
4 Correct 6 ms 1968 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct
7 Correct 6 ms 1968 KB Output is correct
8 Correct 8 ms 1968 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 5 ms 1968 KB Output is correct
13 Correct 7 ms 1968 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 6 ms 2016 KB Output is correct
17 Correct 6 ms 2008 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 1143 ms 116664 KB Output is correct
20 Correct 218 ms 29712 KB Output is correct
21 Correct 805 ms 70492 KB Output is correct
22 Correct 1075 ms 108496 KB Output is correct
23 Correct 1325 ms 121340 KB Output is correct
24 Correct 1369 ms 127952 KB Output is correct
25 Correct 200 ms 21940 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1198 ms 116376 KB Output is correct
2 Correct 1162 ms 119368 KB Output is correct
3 Correct 1375 ms 121008 KB Output is correct
4 Correct 1242 ms 123668 KB Output is correct
5 Correct 1211 ms 115156 KB Output is correct
6 Correct 1373 ms 127132 KB Output is correct
7 Execution timed out 1538 ms 126844 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1218 ms 116356 KB Output is correct
3 Correct 1242 ms 119228 KB Output is correct
4 Correct 1339 ms 120904 KB Output is correct
5 Correct 1264 ms 125088 KB Output is correct
6 Correct 1235 ms 124696 KB Output is correct
7 Correct 1237 ms 121320 KB Output is correct
8 Correct 1118 ms 116056 KB Output is correct
9 Correct 1251 ms 126856 KB Output is correct
10 Correct 1233 ms 118200 KB Output is correct
11 Correct 1187 ms 117308 KB Output is correct
12 Correct 182 ms 34672 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 6 ms 1952 KB Output is correct
16 Correct 6 ms 1968 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 5 ms 1236 KB Output is correct
19 Correct 6 ms 1968 KB Output is correct
20 Correct 8 ms 1968 KB Output is correct
21 Correct 3 ms 468 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 5 ms 1968 KB Output is correct
25 Correct 6 ms 1968 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 5 ms 1236 KB Output is correct
28 Correct 7 ms 1968 KB Output is correct
29 Correct 7 ms 1968 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 44 ms 2392 KB Output is correct
32 Correct 71 ms 7884 KB Output is correct
33 Correct 48 ms 2372 KB Output is correct
34 Correct 43 ms 5348 KB Output is correct
35 Correct 53 ms 8640 KB Output is correct
36 Correct 50 ms 8528 KB Output is correct
37 Correct 70 ms 10772 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 5 ms 1968 KB Output is correct
41 Correct 7 ms 1968 KB Output is correct
42 Correct 2 ms 596 KB Output is correct
43 Correct 4 ms 1236 KB Output is correct
44 Correct 6 ms 2016 KB Output is correct
45 Correct 6 ms 2008 KB Output is correct
46 Correct 2 ms 468 KB Output is correct
47 Correct 1143 ms 116664 KB Output is correct
48 Correct 218 ms 29712 KB Output is correct
49 Correct 805 ms 70492 KB Output is correct
50 Correct 1075 ms 108496 KB Output is correct
51 Correct 1325 ms 121340 KB Output is correct
52 Correct 1369 ms 127952 KB Output is correct
53 Correct 200 ms 21940 KB Output is correct
54 Correct 1198 ms 116376 KB Output is correct
55 Correct 1162 ms 119368 KB Output is correct
56 Correct 1375 ms 121008 KB Output is correct
57 Correct 1242 ms 123668 KB Output is correct
58 Correct 1211 ms 115156 KB Output is correct
59 Correct 1373 ms 127132 KB Output is correct
60 Execution timed out 1538 ms 126844 KB Time limit exceeded
61 Halted 0 ms 0 KB -