oj.uz

Submission #864282

# Submission time Handle Problem Language Result Execution time Memory
864282 2023-10-22T10:09:00 Z danikoynov Event Hopping (BOI22_events) C++14
50 / 100
 1500 ms 20504 KB 
#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;
      
        while(cur >= 0 && viable[cur] >= to)
            cur --;
        cur ++;

        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 19920 KB Output is correct
3 Correct 269 ms 19732 KB Output is correct
4 Correct 280 ms 19868 KB Output is correct
5 Correct 268 ms 19892 KB Output is correct
6 Correct 272 ms 19952 KB Output is correct
7 Correct 265 ms 19836 KB Output is correct
8 Correct 279 ms 20428 KB Output is correct
9 Correct 257 ms 20428 KB Output is correct
10 Correct 278 ms 20116 KB Output is correct
11 Correct 264 ms 20180 KB Output is correct
12 Correct 224 ms 17744 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 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 12632 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 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 12632 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 3 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 12636 KB Output is correct
17 Correct 2 ms 12632 KB Output is correct
18 Correct 2 ms 12632 KB Output is correct
19 Correct 177 ms 13652 KB Output is correct
20 Correct 170 ms 13564 KB Output is correct
21 Correct 166 ms 13816 KB Output is correct
22 Correct 166 ms 13904 KB Output is correct
23 Correct 160 ms 13780 KB Output is correct
24 Correct 155 ms 13652 KB Output is correct
25 Correct 178 ms 14212 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 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 12632 KB Output is correct
8 Correct 3 ms 12636 KB Output is correct
9 Correct 2 ms 12636 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 3 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 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 96 ms 19176 KB Output is correct
20 Correct 83 ms 19392 KB Output is correct
21 Correct 89 ms 16208 KB Output is correct
22 Correct 120 ms 19084 KB Output is correct
23 Correct 89 ms 18792 KB Output is correct
24 Correct 95 ms 19664 KB Output is correct
25 Correct 49 ms 14044 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 19768 KB Output is correct
2 Correct 268 ms 19920 KB Output is correct
3 Correct 280 ms 19920 KB Output is correct
4 Correct 258 ms 20292 KB Output is correct
5 Correct 274 ms 20504 KB Output is correct
6 Correct 274 ms 19916 KB Output is correct
7 Correct 277 ms 20100 KB Output is correct
8 Correct 274 ms 19860 KB Output is correct
9 Correct 90 ms 18776 KB Output is correct
10 Correct 297 ms 19684 KB Output is correct
11 Execution timed out 1560 ms 19388 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 262 ms 19920 KB Output is correct
3 Correct 269 ms 19732 KB Output is correct
4 Correct 280 ms 19868 KB Output is correct
5 Correct 268 ms 19892 KB Output is correct
6 Correct 272 ms 19952 KB Output is correct
7 Correct 265 ms 19836 KB Output is correct
8 Correct 279 ms 20428 KB Output is correct
9 Correct 257 ms 20428 KB Output is correct
10 Correct 278 ms 20116 KB Output is correct
11 Correct 264 ms 20180 KB Output is correct
12 Correct 224 ms 17744 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 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 12632 KB Output is correct
20 Correct 3 ms 12636 KB Output is correct
21 Correct 2 ms 12636 KB Output is correct
22 Correct 2 ms 12636 KB Output is correct
23 Correct 2 ms 12636 KB Output is correct
24 Correct 2 ms 12636 KB Output is correct
25 Correct 3 ms 12636 KB Output is correct
26 Correct 2 ms 12636 KB Output is correct
27 Correct 2 ms 12636 KB Output is correct
28 Correct 2 ms 12636 KB Output is correct
29 Correct 2 ms 12632 KB Output is correct
30 Correct 2 ms 12632 KB Output is correct
31 Correct 177 ms 13652 KB Output is correct
32 Correct 170 ms 13564 KB Output is correct
33 Correct 166 ms 13816 KB Output is correct
34 Correct 166 ms 13904 KB Output is correct
35 Correct 160 ms 13780 KB Output is correct
36 Correct 155 ms 13652 KB Output is correct
37 Correct 178 ms 14212 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 12636 KB Output is correct
41 Correct 3 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 12636 KB Output is correct
45 Correct 3 ms 12636 KB Output is correct
46 Correct 2 ms 12636 KB Output is correct
47 Correct 96 ms 19176 KB Output is correct
48 Correct 83 ms 19392 KB Output is correct
49 Correct 89 ms 16208 KB Output is correct
50 Correct 120 ms 19084 KB Output is correct
51 Correct 89 ms 18792 KB Output is correct
52 Correct 95 ms 19664 KB Output is correct
53 Correct 49 ms 14044 KB Output is correct
54 Correct 263 ms 19768 KB Output is correct
55 Correct 268 ms 19920 KB Output is correct
56 Correct 280 ms 19920 KB Output is correct
57 Correct 258 ms 20292 KB Output is correct
58 Correct 274 ms 20504 KB Output is correct
59 Correct 274 ms 19916 KB Output is correct
60 Correct 277 ms 20100 KB Output is correct
61 Correct 274 ms 19860 KB Output is correct
62 Correct 90 ms 18776 KB Output is correct
63 Correct 297 ms 19684 KB Output is correct
64 Execution timed out 1560 ms 19388 KB Time limit exceeded
65 Halted 0 ms 0 KB -