oj.uz

Submission #653585

# Submission time Handle Problem Language Result Execution time Memory
653585 2022-10-27T11:04:11 Z AlperenT Event Hopping (BOI22_events) C++17
10 / 100
 408 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 5, INF = 1e9 + 5;

int n, q, canmove[N][N];

struct Event{
    int l, r;

    bool operator < (const Event &sc) const{
        if(r == sc.r) return l < sc.l;
        else return r < sc.r;
    }
};

Event arr[N];

vector<pair<Event, int>> v;

struct SegTree{
    int tree[N * 8];

    SegTree(){
        fill(tree, tree + N * 4, INF);
    }

    int merge(int a, int b){
        return min(a, b);
    }

    int query(int l, int r, int v = 1, int tl = 1, int tr = N - 1){
        if(l > r) return INF;
        else if(l == tl && r == tr) return tree[v];
        else{
            int tm = tl + (tr - tl) / 2;

            return merge(query(l, min(tm, r), v * 2, tl, tm), query(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr));
        }
    }

    void update(int pos, int val, int v = 1, int l = 1, int r = N - 1){
        if(l == r) tree[v] = min(tree[v], val);
        else{
            int m = l + (r - l) / 2;

            if(pos <= m) update(pos, val, v * 2, l, m);
            else update(pos, val, v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }
};

map<int, int> cmprs;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            canmove[i][j] = INF;
        }
    }

    cin >> n >> q;

    for(int i = 1; i <= n; i++) cin >> arr[i].l >> arr[i].r;

    for(int i = 1; i <= n; i++) cmprs[arr[i].l] = cmprs[arr[i].r] = 1;

    int tmp = 0;

    for(auto &p : cmprs) p.second = ++tmp;

    for(int i = 1; i <= n; i++) arr[i].l = cmprs[arr[i].l], arr[i].r = cmprs[arr[i].r];

    for(int i = 1; i <= n; i++) v.push_back({arr[i], i});

    sort(v.begin(), v.end());

    map<int, vector<int>> mp;

    for(int i = 1; i <= n; i++) mp[arr[i].r].push_back(i);

    for(auto p : mp){
        for(auto x : p.second){
            for(auto y : p.second){
                canmove[x][y] = 1;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        canmove[i][i] = 0;
    }

    for(int i = 1; i <= n; i++){
        SegTree sgt = SegTree();

        for(auto p : v){
            canmove[p.second][i] = min(canmove[p.second][i], sgt.query(p.first.l, p.first.r) + 1);

            sgt.update(p.first.r, canmove[p.second][i]);
        }
    }

    while(q--){
        int s, e;

        cin >> s >> e;

        if(canmove[e][s] == INF) cout << "impossible\n";
        else cout << canmove[e][s] << "\n"; 
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 98448 KB Output is correct
2 Runtime error 321 ms 233708 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98388 KB Output is correct
2 Correct 58 ms 98396 KB Output is correct
3 Correct 189 ms 98800 KB Output is correct
4 Correct 191 ms 98816 KB Output is correct
5 Correct 179 ms 98688 KB Output is correct
6 Correct 200 ms 98764 KB Output is correct
7 Correct 289 ms 98728 KB Output is correct
8 Correct 260 ms 98748 KB Output is correct
9 Correct 146 ms 98552 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98388 KB Output is correct
2 Correct 58 ms 98396 KB Output is correct
3 Correct 189 ms 98800 KB Output is correct
4 Correct 191 ms 98816 KB Output is correct
5 Correct 179 ms 98688 KB Output is correct
6 Correct 200 ms 98764 KB Output is correct
7 Correct 289 ms 98728 KB Output is correct
8 Correct 260 ms 98748 KB Output is correct
9 Correct 146 ms 98552 KB Output is correct
10 Correct 55 ms 98508 KB Output is correct
11 Correct 47 ms 98472 KB Output is correct
12 Correct 210 ms 98700 KB Output is correct
13 Correct 201 ms 98700 KB Output is correct
14 Correct 191 ms 98684 KB Output is correct
15 Correct 199 ms 98644 KB Output is correct
16 Correct 287 ms 98748 KB Output is correct
17 Correct 270 ms 98752 KB Output is correct
18 Correct 136 ms 98548 KB Output is correct
19 Runtime error 286 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98388 KB Output is correct
2 Correct 58 ms 98396 KB Output is correct
3 Correct 189 ms 98800 KB Output is correct
4 Correct 191 ms 98816 KB Output is correct
5 Correct 179 ms 98688 KB Output is correct
6 Correct 200 ms 98764 KB Output is correct
7 Correct 289 ms 98728 KB Output is correct
8 Correct 260 ms 98748 KB Output is correct
9 Correct 146 ms 98552 KB Output is correct
10 Correct 50 ms 98508 KB Output is correct
11 Correct 51 ms 98504 KB Output is correct
12 Correct 242 ms 98668 KB Output is correct
13 Correct 183 ms 98640 KB Output is correct
14 Correct 187 ms 98684 KB Output is correct
15 Correct 245 ms 98640 KB Output is correct
16 Correct 286 ms 98840 KB Output is correct
17 Correct 268 ms 98636 KB Output is correct
18 Correct 157 ms 98432 KB Output is correct
19 Runtime error 408 ms 234000 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 379 ms 233888 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 98448 KB Output is correct
2 Runtime error 321 ms 233708 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -