oj.uz

Submission #660106

# Submission time Handle Problem Language Result Execution time Memory
660106 2022-11-20T11:11:57 Z Karuk Event Hopping (BOI22_events) C++14
35 / 100
 1500 ms 122868 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.first>b.first?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)>>1;
    return max(ask(from,to,cur<<1,beg,mid),ask(from,to,(cur<<1)|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][20];
    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<20;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=19;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 1261 ms 112448 KB Output is correct
3 Correct 1299 ms 115396 KB Output is correct
4 Correct 1382 ms 117092 KB Output is correct
5 Correct 1214 ms 118120 KB Output is correct
6 Correct 1240 ms 117860 KB Output is correct
7 Correct 1207 ms 114544 KB Output is correct
8 Correct 1109 ms 109032 KB Output is correct
9 Correct 1231 ms 120040 KB Output is correct
10 Correct 1189 ms 111340 KB Output is correct
11 Correct 1181 ms 110264 KB Output is correct
12 Correct 183 ms 28412 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 1840 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 4 ms 1236 KB Output is correct
7 Correct 6 ms 1968 KB Output is correct
8 Correct 7 ms 1968 KB Output is correct
9 Correct 2 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 1840 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 4 ms 1236 KB Output is correct
7 Correct 6 ms 1968 KB Output is correct
8 Correct 7 ms 1968 KB Output is correct
9 Correct 2 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 6 ms 1840 KB Output is correct
13 Correct 5 ms 1968 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 6 ms 1968 KB Output is correct
17 Correct 6 ms 1964 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 35 ms 2108 KB Output is correct
20 Correct 54 ms 7712 KB Output is correct
21 Correct 34 ms 2260 KB Output is correct
22 Correct 41 ms 5208 KB Output is correct
23 Correct 56 ms 8440 KB Output is correct
24 Correct 53 ms 8284 KB Output is correct
25 Correct 63 ms 10568 KB Output is correct

Subtask #4
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 1840 KB Output is correct
4 Correct 6 ms 1972 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 4 ms 1236 KB Output is correct
7 Correct 6 ms 1968 KB Output is correct
8 Correct 7 ms 1968 KB Output is correct
9 Correct 2 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 1840 KB Output is correct
13 Correct 6 ms 1968 KB Output is correct
14 Correct 2 ms 568 KB Output is correct
15 Correct 4 ms 1132 KB Output is correct
16 Correct 6 ms 1968 KB Output is correct
17 Correct 6 ms 1968 KB Output is correct
18 Correct 3 ms 468 KB Output is correct
19 Correct 1198 ms 112732 KB Output is correct
20 Correct 241 ms 25708 KB Output is correct
21 Correct 842 ms 66524 KB Output is correct
22 Correct 1102 ms 104400 KB Output is correct
23 Correct 1370 ms 117292 KB Output is correct
24 Execution timed out 1512 ms 122164 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1253 ms 112380 KB Output is correct
2 Correct 1220 ms 115248 KB Output is correct
3 Correct 1399 ms 116948 KB Output is correct
4 Correct 1292 ms 119792 KB Output is correct
5 Correct 1265 ms 111200 KB Output is correct
6 Correct 1487 ms 122868 KB Output is correct
7 Correct 1465 ms 122848 KB Output is correct
8 Correct 1457 ms 121400 KB Output is correct
9 Correct 1375 ms 117228 KB Output is correct
10 Correct 1436 ms 122524 KB Output is correct
11 Correct 1499 ms 121216 KB Output is correct
12 Execution timed out 1580 ms 122480 KB Time limit exceeded
13 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 1261 ms 112448 KB Output is correct
3 Correct 1299 ms 115396 KB Output is correct
4 Correct 1382 ms 117092 KB Output is correct
5 Correct 1214 ms 118120 KB Output is correct
6 Correct 1240 ms 117860 KB Output is correct
7 Correct 1207 ms 114544 KB Output is correct
8 Correct 1109 ms 109032 KB Output is correct
9 Correct 1231 ms 120040 KB Output is correct
10 Correct 1189 ms 111340 KB Output is correct
11 Correct 1181 ms 110264 KB Output is correct
12 Correct 183 ms 28412 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 1840 KB Output is correct
16 Correct 6 ms 1972 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 4 ms 1236 KB Output is correct
19 Correct 6 ms 1968 KB Output is correct
20 Correct 7 ms 1968 KB Output is correct
21 Correct 2 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 6 ms 1840 KB Output is correct
25 Correct 5 ms 1968 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 4 ms 1236 KB Output is correct
28 Correct 6 ms 1968 KB Output is correct
29 Correct 6 ms 1964 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 35 ms 2108 KB Output is correct
32 Correct 54 ms 7712 KB Output is correct
33 Correct 34 ms 2260 KB Output is correct
34 Correct 41 ms 5208 KB Output is correct
35 Correct 56 ms 8440 KB Output is correct
36 Correct 53 ms 8284 KB Output is correct
37 Correct 63 ms 10568 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 5 ms 1840 KB Output is correct
41 Correct 6 ms 1968 KB Output is correct
42 Correct 2 ms 568 KB Output is correct
43 Correct 4 ms 1132 KB Output is correct
44 Correct 6 ms 1968 KB Output is correct
45 Correct 6 ms 1968 KB Output is correct
46 Correct 3 ms 468 KB Output is correct
47 Correct 1198 ms 112732 KB Output is correct
48 Correct 241 ms 25708 KB Output is correct
49 Correct 842 ms 66524 KB Output is correct
50 Correct 1102 ms 104400 KB Output is correct
51 Correct 1370 ms 117292 KB Output is correct
52 Execution timed out 1512 ms 122164 KB Time limit exceeded
53 Halted 0 ms 0 KB -