oj.uz

Submission #722323

# Submission time Handle Problem Language Result Execution time Memory
722323 2023-04-11T18:22:18 Z drdilyor Event Hopping (BOI22_events) C++17
60 / 100
 752 ms 100592 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
 
const int inf = 1e9 + 1e5;
struct event {
    int l, r, i;
};

struct segtree {
    int n;
    vector<pair<int,int>> t;
    segtree(int n) : n(n), t(n*4, {-1, -1}) {}
    void update(int i, const pair<int,int>& x) {
        t[i+=n] = x;
        for (i /= 2; i >= 1; i/= 2) {
            t[i] = max(t[i*2], t[i*2+1]);
        }
    }
    pair<int,int> query(int l, int r) {
        l += n;
        r += n;
        pair<int,int> res{-1,-1};
        while (l <= r) {
            if (l%2==1) res = max(res, t[l++]);
            if (r%2==0) res = max(res, t[r--]);
            l /= 2;
            r /= 2;
        }
        return res;
    }
};

int subtask_5(int n, int m, int k, vector<event>& ev, vector<event>& og)  {
    segtree mxr(k);

    for (int i = 0; i < n;i ++) {
        mxr.update(ev[i].l, {ev[i].r, i});
    }

    vector jmp(20, vector(n, -1));
    for (int i = 0; i < n; i++) {
        pair<int,int> mx = mxr.query(0, ev[i].r);
        if (mx.first != ev[i].r)
            jmp[0][i] = mx.second;
    }
    for (int j = 1; j < 20; j++)
        for (int i = 0; i < n;i++)
            if (jmp[j-1][i] != -1)
                jmp[j][i] = jmp[j-1][jmp[j-1][i]];

    vector<int> iof(n);
    for (int i = 0; i < n; i++)
        iof[ev[i].i] = i;


    while (m--) {
        int s, e;
        cin >> s >> e;
        s--;e--;
 
        if (s == e) {
            cout << "0\n";
            continue;
        }
        if (og[e].l <= og[s].r && og[s].r <= og[e].r) {
            cout << "1\n";
            continue;
        }
        if (og[e].r < og[s].r) {
            cout << "impossible\n";
            continue;
        }

        int si = iof[s], ei = iof[e];
 
        int res = 0;
        for (int j = 19; j >= 0; j--) {
            if (jmp[j][si] != -1 && ev[jmp[j][si]].r < ev[ei].l) {
                si = jmp[j][si];
                res += 1<<j;
            }
        }
        int j = jmp[0][si];
        if (j != -1 && jmp[0][j] != -1 && ev[ei].l <= ev[jmp[0][j]].r) {
            cout << res+2 << '\n';
        } else {
            cout << "impossible\n";
        }
    }
 
    return 0;
}

int subtask_4(int n, int m, int k, vector<event>& ev, vector<event>& og)  {
 
 
    while (m--) {
        int s, e;
        cin >> s >> e;
        s--;e--;
 
        if (s == e) {
            cout << "0\n";
            continue;
        }
 
 
        int si = 0, ei = 0;
        for (int j = 0; j < n; j++) {
            if (ev[j].i == s) si = j;
            if (ev[j].i == e) ei = j;
        }
 
        int res = 0;
        bool found = 0;
        int left = ev[ei].l;
        set<int> st;
        for (int j = n-1; j >= 0; j--) {
            auto [l,r,_i] = ev[j];
            if (r > ev[ei].r) continue;
            if (r < left) {
                if (st.empty()) break;
                left = *st.begin();
                if (r < left) break;
                st.clear();
                res++;
            }
            if (j == si) {
                res++;
                found = 1;
                break;
            }
            st.insert(l);
            continue;
        }
 
 
        if (found) cout << res << '\n';
        else cout << "impossible\n";
    }
 
    return 0;
}

int subtask_3(int n, int m, int k, vector<event>& ev, vector<event>& og) {
    vector ans(n, vector(n, inf));
    vector<int> mnl(k, inf);
    for (auto [l, r, i] :ev) {
        mnl[r] = min(mnl[r], l);
    }
 
    for (int ei = n-1; ei >= 0; ei--) {
        int res = 0;
        int lb = ev[ei].l, rb = ev[ei].r;
        for (int j = n-1; j >= 0; j--) {
            auto [l,r,_i] = ev[j];
            if (r > ev[ei].r) continue;
            if (r < lb) {
                int mn = inf;
                for (int i = lb; i <= rb; i++)
                    mn = min(mn, mnl[i]);
                lb = mn;
                if (r < lb) break;
                rb = r;
                res++;
            }
            ans[ei][j] = res + 1;
        }
    }
 
    while (m--) {
        int s, e;
        cin >> s >> e;
        s--;e--;
 
        if (s == e) {
            cout << "0\n";
            continue;
        }
 
        int si = 0, ei = 0;
        for (int j = 0; j < n; j++) {
            if (ev[j].i == s) si = j;
            if (ev[j].i == e) ei = j;
        }
 
        if (ans[ei][si] < inf) cout << ans[ei][si] << '\n';
        else cout << "impossible\n";
    }
 
    return 0;
}

int subtask_1(int n, int m, int k, vector<event>& ev, vector<event>& og) {
    vector<vector<int>> byr(k);
    for (int i = 0; i < n;i++) {
        byr[ev[i].r].push_back(i);
    }
    vector next(20, vector(n, -1));
    vector dist(n, inf), cc(n, -1);
    for (int i = 0; i < n;i++) {
        for (int j = ev[i].l; j <= ev[i].r; j++) {
            for (int t : byr[j]) {
                if (t != i)
                    next[0][t] = i;
            }
        }
    }

    int C = 0;
    for (int i = 0; i < n;i++)
        if (next[0][i] != -1)
            cc[i] = cc[next[0][i]];
        else cc[i] = C++;

    for (int j = 1; j < 20; j++) {
        for (int i = 0; i < n; i++) {
            if (next[j-1][i] != -1)
                next[j][i] = next[j-1][next[j-1][i]];
        }
    }

    vector<int> iof(n);
    for (int i = 0; i < n; i++)
        iof[ev[i].i] = i;


    while (m--) {
        int s, e;
        cin >> s >> e;
        s--;e--;
        s = iof[s], e = iof[e];
        int ans = 0;
        if (s == e) {
            cout << "0\n";
            continue;
        }
        for (int j = 20-1; j >= 0; j--) {
            if (next[j][s] != -1 && next[j][s] < e) {
                s = next[j][s];
                ans += 1<<j;
            }
        }
        if (next[0][s] != -1 && next[0][s] == e)
            cout << ans+1 << '\n';
        else cout << "impossible\n";
    }

    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<event> ev(n), og;
    map<int,int> comp;
    int _i = 0;
    for (auto& [s, e, i] : ev) {
        cin >> s >> e;
        comp[s] = comp[e] = 0;
        i = _i++;
    }
    int k = 0;
    for (auto& mp : comp)
        mp.second = k++;
    for (auto& [s, e, i] : ev)
        s = comp[s], e = comp[e];
 
    og = ev;
    sort(ev.begin(), ev.end(), [&](auto& a, auto& b) {
        return a.r == b.r ? a.l < b.l : a.r < b.r ;
    });

    bool overlap = 0;
    for (int i = 0; i+1 < n;i ++) {
        if (ev[i].l > ev[i+1].l) overlap = 1;
    }
    //for (auto[a,b,c] : ev) cout << a << ' ' << b << ' ' << c <<'\n';
    //return subtask_1(n, m, k, ev, og);
    if (!overlap) return subtask_5(n, m, k, ev, og);
    else if (n <= 5000) return subtask_3(n, m, k, ev, og);
    else if (m <= 100) return subtask_4(n, m, k, ev, og);
    else return subtask_1(n, m, k, ev, og);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 395 ms 22440 KB Output is correct
3 Correct 427 ms 22456 KB Output is correct
4 Correct 404 ms 22516 KB Output is correct
5 Correct 399 ms 26288 KB Output is correct
6 Correct 400 ms 26892 KB Output is correct
7 Incorrect 398 ms 27192 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 5 ms 4332 KB Output is correct
6 Correct 6 ms 4336 KB Output is correct
7 Correct 7 ms 4392 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 5 ms 4332 KB Output is correct
6 Correct 6 ms 4336 KB Output is correct
7 Correct 7 ms 4392 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 436 KB Output is correct
14 Correct 7 ms 4308 KB Output is correct
15 Correct 5 ms 4308 KB Output is correct
16 Correct 7 ms 4308 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 202 ms 2780 KB Output is correct
20 Correct 206 ms 2652 KB Output is correct
21 Correct 752 ms 100336 KB Output is correct
22 Correct 704 ms 100532 KB Output is correct
23 Correct 727 ms 100592 KB Output is correct
24 Correct 174 ms 3256 KB Output is correct
25 Correct 202 ms 3112 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 5 ms 4332 KB Output is correct
6 Correct 6 ms 4336 KB Output is correct
7 Correct 7 ms 4392 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 5 ms 4308 KB Output is correct
15 Correct 6 ms 4268 KB Output is correct
16 Correct 6 ms 4336 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 238 ms 20612 KB Output is correct
20 Correct 242 ms 8404 KB Output is correct
21 Correct 551 ms 11444 KB Output is correct
22 Correct 245 ms 11056 KB Output is correct
23 Correct 282 ms 28452 KB Output is correct
24 Correct 294 ms 28616 KB Output is correct
25 Correct 63 ms 12080 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 22420 KB Output is correct
2 Correct 377 ms 22488 KB Output is correct
3 Correct 394 ms 22324 KB Output is correct
4 Correct 447 ms 30680 KB Output is correct
5 Correct 481 ms 22760 KB Output is correct
6 Correct 512 ms 30340 KB Output is correct
7 Correct 524 ms 30276 KB Output is correct
8 Correct 509 ms 30460 KB Output is correct
9 Correct 255 ms 28408 KB Output is correct
10 Correct 462 ms 29924 KB Output is correct
11 Correct 494 ms 29780 KB Output is correct
12 Correct 491 ms 30036 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 395 ms 22440 KB Output is correct
3 Correct 427 ms 22456 KB Output is correct
4 Correct 404 ms 22516 KB Output is correct
5 Correct 399 ms 26288 KB Output is correct
6 Correct 400 ms 26892 KB Output is correct
7 Incorrect 398 ms 27192 KB Output isn't correct
8 Halted 0 ms 0 KB -