Submission #864283

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
864283	2023-10-22T10:10:28 Z	danikoynov	Event Hopping (BOI22_events)	C++14	100 / 100	295 ms	23516 KB

events

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;
     
struct interval
{
    int s, e, idx;
}seg[maxn];
     
struct query
{
    int start, finish, idx;
}task[maxn];

bool cmp_finish(query q1, query q2)
{
    return q1.finish < q2.finish;
}
int n, q;   


void input()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
    {
        cin >> seg[i].s >> seg[i].e;
        seg[i].idx = i;
    }
    for (int i = 1; i <= q; i ++)
    {
        cin >> task[i].start >> task[i].finish;
        task[i].idx = i;
    }
}



bool cmp_end(interval seg1, interval seg2)
{
    return seg1.e < seg2.e;
}

int lf[maxn], rev[maxn], rf[maxn], ans[maxn];
map < int, int > fix;
void build_graph()
{
    sort(seg + 1, seg + n + 1, cmp_end);
    for (int i = 1; i <= n; i ++)
    {
        rev[seg[i].idx] = i;
    }

    for (int i = 1; i <= n; i ++)
    {
        int l = 1;
        int r = i;
        while(l <= r)
        {
            int m = (l + r) / 2;
            if (seg[m].e < seg[i].s)
                l = m + 1;
            else
                r = m - 1;
        }
        lf[i] = l;
        //while(seg[lf[i]].e < seg[i].s)
           // lf[i] ++;


        if (fix[seg[i].e] == 0)
            fix[seg[i].e] = lf[i];
        else
            fix[seg[i].e] = min(fix[seg[i].e], lf[i]);
    }
}

const int maxlog = 21;
int dp[maxlog][maxn];

int tree[4 * maxn];
void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root] = lf[left];
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = min(tree[root * 2], tree[root * 2 + 1]);
}

int query_min(int root, int left, int right, int qleft, int qright)
{
    //cout << root << "  " << left << " " << right << " " << qleft << " " << qright << endl;
    //assert(root >= 0);
    if (qleft > right || qright < left)
        return 1e9;

if (left >= qleft && right <= qright)
    return tree[root];

int mid = (left + right) / 2;
return min(query_min(root * 2, left, mid, qleft, qright),
        query_min(root * 2 + 1, mid + 1, right, qleft, qright));
}
void answer_queries()
{
    for (int i = 1; i <= q; i ++)
    {
        task[i].start = rev[task[i].start];
        task[i].finish = rev[task[i].finish];
    }
    sort(task + 1, task + q + 1, cmp_finish);
    /**cout << "----------------------" << endl;
    for (int i = 1; i <= n; i ++)
        cout << seg[i].s << " :: " << seg[i].e << endl;*/
    build_tree(1, 1, n);
    vector < int > viable;

    int pt = 1;
    for (int i = 1; i <= q; i ++)
    {

        int st = task[i].start, en = task[i].finish;

        while(pt <= en)
        {
            
            while(!viable.empty() && lf[viable.back()] >= lf[pt])
                viable.pop_back();
            
            int l = 0, r = (int)(viable.size()) - 1;
            while(l <= r)
            {
                int m = (l + r) / 2;
                if (viable[m] < lf[pt])
                    l = m + 1;
                else
                    r = m - 1;
            }
            if (l >= viable.size())
                dp[0][pt] = pt;
            else
                dp[0][pt] = viable[l];

            for (int j = 1; j < maxlog; j ++)
            {
                dp[j][pt] = dp[j - 1][dp[j - 1][pt]];
            }

            viable.push_back(pt);
            
            pt ++;
        }
    if (st == en)
        {
            ans[task[i].idx] = 0;
            continue;
        }
        if (seg[st].e == seg[en].e && st != en)
        {
            ans[task[i].idx] = 1;
            continue;
        }
        
        if (st > en)
        {
            ans[task[i].idx] = -1;
            continue;
        }

        if (st >= lf[en])
        {
            ans[task[i].idx] = 1;
            continue;
        }

        

        int to = fix[seg[en].e];
        to = min(to, query_min(1, 1, n, lf[en], en));
        //for (int i = lf[en]; i <= en; i ++)
          //  to = min(to, lf[i]);
        int steps = 1;

        bool done = false;
        int cur = viable.size() - 1;
      
      int l = 0, r = (int)(viable.size()) - 1;
      while(l <= r)
      {
        int m = (l + r) / 2;
        if (viable[m] >= to)
        r = m - 1;
    else
    l = m + 1;
      }
        cur = l;

        if (st >= to)
        {
            ans[task[i].idx] = 2;
            continue;
        }
        if (lf[viable[cur]] >= to)
        {
            ans[task[i].idx] = -1;
                continue;
        }
        steps ++;
         
        int jump = 0, ver = viable[cur];
        if (st >= lf[ver])
        {
       
            ans[task[i].idx] = steps + 1;
            continue;
        }
        ///cout << "here " << task[i].idx << endl;
        for (int bit = maxlog - 1; bit >= 0; bit --)
        {
            if (lf[dp[bit][ver]] > st)
            {
                ver = dp[bit][ver];
                jump |= (1 << bit);
            }
        }

        jump ++;
        ver = dp[0][ver];
        
        if (st >= lf[ver])
        {
            ///cout << "HERE " << task[i].idx << endl;
            ans[task[i].idx] = steps + jump + 1;
        }
        else
        {
            ans[task[i].idx] = -1;
        }

        
            

            


    }

    for (int i = 1; i <= q; i ++)
    {
        if (ans[i] != - 1)
            cout << ans[i] << endl;
        else
            cout << "impossible" << endl;
    }
}
void solve()
{  
    input();
    build_graph();
    answer_queries();
}

int main()
{   
    ///speed();
    solve();

    return 0;
}

Compilation message

events.cpp: In function 'void answer_queries()':
events.cpp:148:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |             if (l >= viable.size())
      |                 ~~^~~~~~~~~~~~~~~~
events.cpp:193:14: warning: unused variable 'done' [-Wunused-variable]
  193 |         bool done = false;
      |              ^~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	12632 KB	Output is correct
2	Correct	262 ms	19792 KB	Output is correct
3	Correct	269 ms	19704 KB	Output is correct
4	Correct	282 ms	20136 KB	Output is correct
5	Correct	265 ms	19824 KB	Output is correct
6	Correct	274 ms	20024 KB	Output is correct
7	Correct	265 ms	19920 KB	Output is correct
8	Correct	263 ms	20400 KB	Output is correct
9	Correct	258 ms	20428 KB	Output is correct
10	Correct	267 ms	20168 KB	Output is correct
11	Correct	268 ms	20120 KB	Output is correct
12	Correct	225 ms	17732 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	12636 KB	Output is correct
2	Correct	1 ms	12748 KB	Output is correct
3	Correct	2 ms	12636 KB	Output is correct
4	Correct	2 ms	12636 KB	Output is correct
5	Correct	2 ms	12636 KB	Output is correct
6	Correct	2 ms	12636 KB	Output is correct
7	Correct	2 ms	12636 KB	Output is correct
8	Correct	2 ms	12636 KB	Output is correct
9	Correct	2 ms	12632 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	12636 KB	Output is correct
2	Correct	1 ms	12748 KB	Output is correct
3	Correct	2 ms	12636 KB	Output is correct
4	Correct	2 ms	12636 KB	Output is correct
5	Correct	2 ms	12636 KB	Output is correct
6	Correct	2 ms	12636 KB	Output is correct
7	Correct	2 ms	12636 KB	Output is correct
8	Correct	2 ms	12636 KB	Output is correct
9	Correct	2 ms	12632 KB	Output is correct
10	Correct	1 ms	12636 KB	Output is correct
11	Correct	1 ms	12636 KB	Output is correct
12	Correct	2 ms	12636 KB	Output is correct
13	Correct	2 ms	12824 KB	Output is correct
14	Correct	2 ms	12632 KB	Output is correct
15	Correct	2 ms	12636 KB	Output is correct
16	Correct	3 ms	12636 KB	Output is correct
17	Correct	3 ms	12636 KB	Output is correct
18	Correct	2 ms	12636 KB	Output is correct
19	Correct	182 ms	13412 KB	Output is correct
20	Correct	170 ms	13564 KB	Output is correct
21	Correct	168 ms	13908 KB	Output is correct
22	Correct	159 ms	13724 KB	Output is correct
23	Correct	159 ms	13652 KB	Output is correct
24	Correct	160 ms	13752 KB	Output is correct
25	Correct	168 ms	13392 KB	Output is correct

Subtask #4

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	12636 KB	Output is correct
2	Correct	1 ms	12748 KB	Output is correct
3	Correct	2 ms	12636 KB	Output is correct
4	Correct	2 ms	12636 KB	Output is correct
5	Correct	2 ms	12636 KB	Output is correct
6	Correct	2 ms	12636 KB	Output is correct
7	Correct	2 ms	12636 KB	Output is correct
8	Correct	2 ms	12636 KB	Output is correct
9	Correct	2 ms	12632 KB	Output is correct
10	Correct	1 ms	12636 KB	Output is correct
11	Correct	1 ms	12636 KB	Output is correct
12	Correct	2 ms	12888 KB	Output is correct
13	Correct	2 ms	12636 KB	Output is correct
14	Correct	2 ms	12636 KB	Output is correct
15	Correct	2 ms	12636 KB	Output is correct
16	Correct	2 ms	12632 KB	Output is correct
17	Correct	2 ms	12636 KB	Output is correct
18	Correct	2 ms	12636 KB	Output is correct
19	Correct	93 ms	19388 KB	Output is correct
20	Correct	78 ms	19320 KB	Output is correct
21	Correct	90 ms	16228 KB	Output is correct
22	Correct	92 ms	19060 KB	Output is correct
23	Correct	92 ms	18680 KB	Output is correct
24	Correct	108 ms	19412 KB	Output is correct
25	Correct	49 ms	13904 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	264 ms	19936 KB	Output is correct
2	Correct	268 ms	19920 KB	Output is correct
3	Correct	284 ms	19920 KB	Output is correct
4	Correct	265 ms	20432 KB	Output is correct
5	Correct	272 ms	20268 KB	Output is correct
6	Correct	271 ms	20072 KB	Output is correct
7	Correct	269 ms	19920 KB	Output is correct
8	Correct	268 ms	19824 KB	Output is correct
9	Correct	89 ms	18772 KB	Output is correct
10	Correct	267 ms	19712 KB	Output is correct
11	Correct	272 ms	19396 KB	Output is correct
12	Correct	268 ms	22476 KB	Output is correct

Subtask #6

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	12632 KB	Output is correct
2	Correct	262 ms	19792 KB	Output is correct
3	Correct	269 ms	19704 KB	Output is correct
4	Correct	282 ms	20136 KB	Output is correct
5	Correct	265 ms	19824 KB	Output is correct
6	Correct	274 ms	20024 KB	Output is correct
7	Correct	265 ms	19920 KB	Output is correct
8	Correct	263 ms	20400 KB	Output is correct
9	Correct	258 ms	20428 KB	Output is correct
10	Correct	267 ms	20168 KB	Output is correct
11	Correct	268 ms	20120 KB	Output is correct
12	Correct	225 ms	17732 KB	Output is correct
13	Correct	1 ms	12636 KB	Output is correct
14	Correct	1 ms	12748 KB	Output is correct
15	Correct	2 ms	12636 KB	Output is correct
16	Correct	2 ms	12636 KB	Output is correct
17	Correct	2 ms	12636 KB	Output is correct
18	Correct	2 ms	12636 KB	Output is correct
19	Correct	2 ms	12636 KB	Output is correct
20	Correct	2 ms	12636 KB	Output is correct
21	Correct	2 ms	12632 KB	Output is correct
22	Correct	1 ms	12636 KB	Output is correct
23	Correct	1 ms	12636 KB	Output is correct
24	Correct	2 ms	12636 KB	Output is correct
25	Correct	2 ms	12824 KB	Output is correct
26	Correct	2 ms	12632 KB	Output is correct
27	Correct	2 ms	12636 KB	Output is correct
28	Correct	3 ms	12636 KB	Output is correct
29	Correct	3 ms	12636 KB	Output is correct
30	Correct	2 ms	12636 KB	Output is correct
31	Correct	182 ms	13412 KB	Output is correct
32	Correct	170 ms	13564 KB	Output is correct
33	Correct	168 ms	13908 KB	Output is correct
34	Correct	159 ms	13724 KB	Output is correct
35	Correct	159 ms	13652 KB	Output is correct
36	Correct	160 ms	13752 KB	Output is correct
37	Correct	168 ms	13392 KB	Output is correct
38	Correct	1 ms	12636 KB	Output is correct
39	Correct	1 ms	12636 KB	Output is correct
40	Correct	2 ms	12888 KB	Output is correct
41	Correct	2 ms	12636 KB	Output is correct
42	Correct	2 ms	12636 KB	Output is correct
43	Correct	2 ms	12636 KB	Output is correct
44	Correct	2 ms	12632 KB	Output is correct
45	Correct	2 ms	12636 KB	Output is correct
46	Correct	2 ms	12636 KB	Output is correct
47	Correct	93 ms	19388 KB	Output is correct
48	Correct	78 ms	19320 KB	Output is correct
49	Correct	90 ms	16228 KB	Output is correct
50	Correct	92 ms	19060 KB	Output is correct
51	Correct	92 ms	18680 KB	Output is correct
52	Correct	108 ms	19412 KB	Output is correct
53	Correct	49 ms	13904 KB	Output is correct
54	Correct	264 ms	19936 KB	Output is correct
55	Correct	268 ms	19920 KB	Output is correct
56	Correct	284 ms	19920 KB	Output is correct
57	Correct	265 ms	20432 KB	Output is correct
58	Correct	272 ms	20268 KB	Output is correct
59	Correct	271 ms	20072 KB	Output is correct
60	Correct	269 ms	19920 KB	Output is correct
61	Correct	268 ms	19824 KB	Output is correct
62	Correct	89 ms	18772 KB	Output is correct
63	Correct	267 ms	19712 KB	Output is correct
64	Correct	272 ms	19396 KB	Output is correct
65	Correct	268 ms	22476 KB	Output is correct
66	Correct	1 ms	12636 KB	Output is correct
67	Correct	271 ms	23080 KB	Output is correct
68	Correct	295 ms	22992 KB	Output is correct
69	Correct	292 ms	23000 KB	Output is correct
70	Correct	268 ms	23056 KB	Output is correct
71	Correct	277 ms	22988 KB	Output is correct
72	Correct	270 ms	22952 KB	Output is correct
73	Correct	261 ms	23504 KB	Output is correct
74	Correct	267 ms	23516 KB	Output is correct
75	Correct	268 ms	23304 KB	Output is correct
76	Correct	267 ms	23120 KB	Output is correct
77	Correct	230 ms	20000 KB	Output is correct
78	Correct	2 ms	12636 KB	Output is correct
79	Correct	2 ms	12636 KB	Output is correct
80	Correct	2 ms	12840 KB	Output is correct
81	Correct	2 ms	12632 KB	Output is correct
82	Correct	3 ms	12636 KB	Output is correct
83	Correct	2 ms	12636 KB	Output is correct
84	Correct	2 ms	12636 KB	Output is correct
85	Correct	2 ms	12764 KB	Output is correct
86	Correct	179 ms	14424 KB	Output is correct
87	Correct	170 ms	14676 KB	Output is correct
88	Correct	166 ms	14932 KB	Output is correct
89	Correct	165 ms	14956 KB	Output is correct
90	Correct	160 ms	14784 KB	Output is correct
91	Correct	156 ms	14716 KB	Output is correct
92	Correct	169 ms	14440 KB	Output is correct
93	Correct	94 ms	21204 KB	Output is correct
94	Correct	79 ms	20432 KB	Output is correct
95	Correct	90 ms	18256 KB	Output is correct
96	Correct	93 ms	21072 KB	Output is correct
97	Correct	98 ms	20816 KB	Output is correct
98	Correct	93 ms	21204 KB	Output is correct
99	Correct	54 ms	15188 KB	Output is correct
100	Correct	273 ms	22984 KB	Output is correct
101	Correct	270 ms	22992 KB	Output is correct
102	Correct	270 ms	22988 KB	Output is correct
103	Correct	277 ms	22980 KB	Output is correct
104	Correct	274 ms	22480 KB	Output is correct
105	Correct	273 ms	22928 KB	Output is correct
106	Correct	253 ms	21196 KB	Output is correct
107	Correct	261 ms	22476 KB	Output is correct
108	Correct	261 ms	20244 KB	Output is correct
109	Correct	256 ms	20152 KB	Output is correct
110	Correct	265 ms	22412 KB	Output is correct
111	Correct	265 ms	22356 KB	Output is correct