oj.uz

Submission #721911

# Submission time Handle Problem Language Result Execution time Memory
721911 2023-04-11T08:47:19 Z drdilyor Event Hopping (BOI22_events) C++17
60 / 100
 804 ms 99952 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<int> next(n, -1), dist(n, inf), cc(n, -1);
    for (int i = 1; i < n; i++) {
        if (ev[i-1].l <= ev[i].r)
            next[i-1] = i;
    }
    cc[n-1] = 0;
    for (int i = n-2; i >= 0; i--) {
        if (next[i] !=-1) {
            dist[i] = min(dist[i], 1 + dist[next[i]]);
            cc[i] = cc[i+1];
        }
        else cc[i] = cc[i+1]+1;
    }

    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];
        if (cc[s] != cc[e] || dist[s] < dist[e]) cout << "impossible\n";
        else cout << dist[s] - dist[e] << '\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';
    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 0 ms 212 KB Output is correct
2 Correct 404 ms 19300 KB Output is correct
3 Correct 389 ms 19380 KB Output is correct
4 Correct 404 ms 19340 KB Output is correct
5 Incorrect 354 ms 9688 KB Output isn't correct
6 Halted 0 ms 0 KB -

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 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 5 ms 4324 KB Output is correct
6 Correct 6 ms 4308 KB Output is correct
7 Correct 6 ms 4308 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 340 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 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 5 ms 4324 KB Output is correct
6 Correct 6 ms 4308 KB Output is correct
7 Correct 6 ms 4308 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 484 KB Output is correct
14 Correct 5 ms 4308 KB Output is correct
15 Correct 6 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 1 ms 340 KB Output is correct
19 Correct 196 ms 1800 KB Output is correct
20 Correct 186 ms 1716 KB Output is correct
21 Correct 694 ms 99452 KB Output is correct
22 Correct 758 ms 99948 KB Output is correct
23 Correct 804 ms 99952 KB Output is correct
24 Correct 182 ms 2376 KB Output is correct
25 Correct 183 ms 2124 KB Output is correct

Subtask #4
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 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 5 ms 4324 KB Output is correct
6 Correct 6 ms 4308 KB Output is correct
7 Correct 6 ms 4308 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 6 ms 4308 KB Output is correct
15 Correct 6 ms 4308 KB Output is correct
16 Correct 6 ms 4380 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 184 ms 18664 KB Output is correct
20 Correct 225 ms 7256 KB Output is correct
21 Correct 499 ms 9948 KB Output is correct
22 Correct 238 ms 9504 KB Output is correct
23 Correct 226 ms 26760 KB Output is correct
24 Correct 282 ms 26652 KB Output is correct
25 Correct 64 ms 11096 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 19268 KB Output is correct
2 Correct 362 ms 19316 KB Output is correct
3 Correct 384 ms 19396 KB Output is correct
4 Correct 414 ms 27564 KB Output is correct
5 Correct 431 ms 19616 KB Output is correct
6 Correct 501 ms 27268 KB Output is correct
7 Correct 542 ms 27400 KB Output is correct
8 Correct 452 ms 27332 KB Output is correct
9 Correct 263 ms 26604 KB Output is correct
10 Correct 455 ms 26976 KB Output is correct
11 Correct 511 ms 26752 KB Output is correct
12 Correct 465 ms 26960 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 404 ms 19300 KB Output is correct
3 Correct 389 ms 19380 KB Output is correct
4 Correct 404 ms 19340 KB Output is correct
5 Incorrect 354 ms 9688 KB Output isn't correct
6 Halted 0 ms 0 KB -