oj.uz

Submission #593936

# Submission time Handle Problem Language Result Execution time Memory
593936 2022-07-11T17:44:21 Z azberjibiou Event Hopping (BOI22_events) C++17
100 / 100
 1185 ms 14244 KB 
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
const int mxN=100010;
const int MOD=1e9+7;
int N, Q, M;
pii A[mxN];
vector <int> coor;
int sps[mxN][20];
int mins[mxN];
int ans[mxN];
pii rng[mxN];
pii qry[mxN];
void make_coor()
{
    for(int i=1;i<=N;i++)   coor.push_back(A[i].sec);
    sort(coor.begin(), coor.end());
    coor.erase(unique(coor.begin(), coor.end()), coor.end());
    for(int i=1;i<=N;i++)   A[i].fir=lower_bound(coor.begin(), coor.end(), A[i].fir)-coor.begin();
    for(int i=1;i<=N;i++)   A[i].sec=lower_bound(coor.begin(), coor.end(), A[i].sec)-coor.begin();
    M=coor.size();
}
int seg[4*mxN];
void init(int idx, int s, int e)
{
    if(s==e)
    {
        seg[idx]=mins[s];
        return;
    }
    int mid=(s+e)/2;
    init(2*idx, s, mid);
    init(2*idx+1, mid+1, e);
    seg[idx]=min(seg[2*idx], seg[2*idx+1]);
}
int solv(int idx, int s1, int e1, int s2, int e2)
{
    if(s2>e1 || s1>e2)  return M;
    if(s2<=s1 && e1<=e2)    return seg[idx];
    int mid=(s1+e1)/2;
    return min(solv(2*idx, s1, mid, s2, e2), solv(2*idx+1, mid+1, e1, s2, e2));
}
int main()
{
    gibon
    cin >> N >> Q;
    for(int i=1;i<=N;i++)   cin >> A[i].fir >> A[i].sec;
    make_coor();
    for(int i=1;i<=N;i++)   sps[i][0]=A[i].fir;
    for(int i=1;i<20;i++)
    {
        for(int j=0;j<M;j++)    mins[j]=M;
        for(int j=1;j<=N;j++)   mins[A[j].sec]=min(mins[A[j].sec], sps[j][i-1]);
        init(1, 0, M-1);
        for(int j=1;j<=N;j++)   sps[j][i]=solv(1, 0, M-1, sps[j][i-1], A[j].sec);
    }
    for(int i=1;i<=Q;i++)   cin >> qry[i].fir >> qry[i].sec;
    for(int i=1;i<=Q;i++)   rng[i]=A[qry[i].sec];
    for(int i=19;i>=0;i--)
    {
        for(int j=0;j<M;j++)    mins[j]=M;
        for(int j=1;j<=N;j++)   mins[A[j].sec]=min(mins[A[j].sec], sps[j][i]);
        init(1, 0, M-1);
        for(int j=1;j<=Q;j++)
        {
            int res=solv(1, 0, M-1, rng[j].fir, rng[j].sec);
            if(res>A[qry[j].fir].sec)   ans[j]+=(1<<i), rng[j].fir=res;
        }
    }
    for(int i=1;i<=Q;i++)
    {
        if(sps[qry[i].sec][19]>A[qry[i].fir].sec || A[qry[i].sec].sec<A[qry[i].fir].sec)    cout << "impossible\n";
        else if(qry[i].sec==qry[i].fir) cout << "0\n";
        else if(A[qry[i].sec].fir<=A[qry[i].fir].sec)   cout << "1\n";
        else    cout << ans[i]+2 << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 614 ms 13736 KB Output is correct
3 Correct 773 ms 13728 KB Output is correct
4 Correct 816 ms 13828 KB Output is correct
5 Correct 757 ms 13772 KB Output is correct
6 Correct 771 ms 13824 KB Output is correct
7 Correct 769 ms 13820 KB Output is correct
8 Correct 540 ms 14240 KB Output is correct
9 Correct 544 ms 14208 KB Output is correct
10 Correct 850 ms 14244 KB Output is correct
11 Correct 872 ms 14236 KB Output is correct
12 Correct 350 ms 13536 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 472 KB Output is correct
4 Correct 3 ms 472 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 356 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 472 KB Output is correct
4 Correct 3 ms 472 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Correct 3 ms 476 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 4 ms 344 KB Output is correct
19 Correct 249 ms 3804 KB Output is correct
20 Correct 238 ms 3660 KB Output is correct
21 Correct 313 ms 3940 KB Output is correct
22 Correct 288 ms 3928 KB Output is correct
23 Correct 389 ms 3636 KB Output is correct
24 Correct 222 ms 3492 KB Output is correct
25 Correct 230 ms 3496 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 472 KB Output is correct
4 Correct 3 ms 472 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 3 ms 488 KB Output is correct
14 Correct 4 ms 456 KB Output is correct
15 Correct 3 ms 352 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 2 ms 356 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 466 ms 11260 KB Output is correct
20 Correct 471 ms 11280 KB Output is correct
21 Correct 375 ms 10560 KB Output is correct
22 Correct 449 ms 11264 KB Output is correct
23 Correct 408 ms 11264 KB Output is correct
24 Correct 493 ms 11392 KB Output is correct
25 Correct 58 ms 9800 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 13792 KB Output is correct
2 Correct 872 ms 13696 KB Output is correct
3 Correct 919 ms 13720 KB Output is correct
4 Correct 613 ms 14212 KB Output is correct
5 Correct 1012 ms 14112 KB Output is correct
6 Correct 1008 ms 13856 KB Output is correct
7 Correct 969 ms 13852 KB Output is correct
8 Correct 1049 ms 14096 KB Output is correct
9 Correct 374 ms 11260 KB Output is correct
10 Correct 853 ms 13600 KB Output is correct
11 Correct 741 ms 13312 KB Output is correct
12 Correct 829 ms 13584 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 614 ms 13736 KB Output is correct
3 Correct 773 ms 13728 KB Output is correct
4 Correct 816 ms 13828 KB Output is correct
5 Correct 757 ms 13772 KB Output is correct
6 Correct 771 ms 13824 KB Output is correct
7 Correct 769 ms 13820 KB Output is correct
8 Correct 540 ms 14240 KB Output is correct
9 Correct 544 ms 14208 KB Output is correct
10 Correct 850 ms 14244 KB Output is correct
11 Correct 872 ms 14236 KB Output is correct
12 Correct 350 ms 13536 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 3 ms 472 KB Output is correct
16 Correct 3 ms 472 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 3 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 1 ms 356 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 4 ms 468 KB Output is correct
26 Correct 5 ms 468 KB Output is correct
27 Correct 3 ms 476 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 4 ms 344 KB Output is correct
31 Correct 249 ms 3804 KB Output is correct
32 Correct 238 ms 3660 KB Output is correct
33 Correct 313 ms 3940 KB Output is correct
34 Correct 288 ms 3928 KB Output is correct
35 Correct 389 ms 3636 KB Output is correct
36 Correct 222 ms 3492 KB Output is correct
37 Correct 230 ms 3496 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 3 ms 468 KB Output is correct
41 Correct 3 ms 488 KB Output is correct
42 Correct 4 ms 456 KB Output is correct
43 Correct 3 ms 352 KB Output is correct
44 Correct 3 ms 468 KB Output is correct
45 Correct 2 ms 356 KB Output is correct
46 Correct 1 ms 468 KB Output is correct
47 Correct 466 ms 11260 KB Output is correct
48 Correct 471 ms 11280 KB Output is correct
49 Correct 375 ms 10560 KB Output is correct
50 Correct 449 ms 11264 KB Output is correct
51 Correct 408 ms 11264 KB Output is correct
52 Correct 493 ms 11392 KB Output is correct
53 Correct 58 ms 9800 KB Output is correct
54 Correct 803 ms 13792 KB Output is correct
55 Correct 872 ms 13696 KB Output is correct
56 Correct 919 ms 13720 KB Output is correct
57 Correct 613 ms 14212 KB Output is correct
58 Correct 1012 ms 14112 KB Output is correct
59 Correct 1008 ms 13856 KB Output is correct
60 Correct 969 ms 13852 KB Output is correct
61 Correct 1049 ms 14096 KB Output is correct
62 Correct 374 ms 11260 KB Output is correct
63 Correct 853 ms 13600 KB Output is correct
64 Correct 741 ms 13312 KB Output is correct
65 Correct 829 ms 13584 KB Output is correct
66 Correct 0 ms 340 KB Output is correct
67 Correct 662 ms 13724 KB Output is correct
68 Correct 843 ms 13732 KB Output is correct
69 Correct 909 ms 13740 KB Output is correct
70 Correct 870 ms 13860 KB Output is correct
71 Correct 818 ms 13860 KB Output is correct
72 Correct 853 ms 13920 KB Output is correct
73 Correct 673 ms 14244 KB Output is correct
74 Correct 583 ms 14240 KB Output is correct
75 Correct 951 ms 14140 KB Output is correct
76 Correct 950 ms 14112 KB Output is correct
77 Correct 349 ms 13540 KB Output is correct
78 Correct 0 ms 340 KB Output is correct
79 Correct 3 ms 468 KB Output is correct
80 Correct 3 ms 492 KB Output is correct
81 Correct 3 ms 468 KB Output is correct
82 Correct 4 ms 468 KB Output is correct
83 Correct 3 ms 468 KB Output is correct
84 Correct 4 ms 356 KB Output is correct
85 Correct 1 ms 468 KB Output is correct
86 Correct 286 ms 3704 KB Output is correct
87 Correct 253 ms 3748 KB Output is correct
88 Correct 354 ms 4008 KB Output is correct
89 Correct 337 ms 3972 KB Output is correct
90 Correct 461 ms 3576 KB Output is correct
91 Correct 259 ms 3500 KB Output is correct
92 Correct 257 ms 3492 KB Output is correct
93 Correct 548 ms 11268 KB Output is correct
94 Correct 509 ms 11340 KB Output is correct
95 Correct 385 ms 10560 KB Output is correct
96 Correct 467 ms 11332 KB Output is correct
97 Correct 374 ms 11264 KB Output is correct
98 Correct 504 ms 11292 KB Output is correct
99 Correct 56 ms 9800 KB Output is correct
100 Correct 998 ms 14028 KB Output is correct
101 Correct 1027 ms 13948 KB Output is correct
102 Correct 1134 ms 13988 KB Output is correct
103 Correct 833 ms 13564 KB Output is correct
104 Correct 869 ms 13412 KB Output is correct
105 Correct 845 ms 13600 KB Output is correct
106 Correct 928 ms 13756 KB Output is correct
107 Correct 1173 ms 13988 KB Output is correct
108 Correct 936 ms 13280 KB Output is correct
109 Correct 959 ms 13244 KB Output is correct
110 Correct 1110 ms 13464 KB Output is correct
111 Correct 1185 ms 13472 KB Output is correct