oj.uz

Submission #653586

# Submission time Handle Problem Language Result Execution time Memory
653586 2022-10-27T11:05:12 Z AlperenT Event Hopping (BOI22_events) C++17
10 / 100
 338 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 * 8, 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 44 ms 98516 KB Output is correct
2 Runtime error 272 ms 233916 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 44 ms 98452 KB Output is correct
2 Correct 45 ms 98400 KB Output is correct
3 Correct 185 ms 98676 KB Output is correct
4 Correct 190 ms 98704 KB Output is correct
5 Correct 197 ms 98692 KB Output is correct
6 Correct 198 ms 98764 KB Output is correct
7 Correct 278 ms 98844 KB Output is correct
8 Correct 258 ms 98748 KB Output is correct
9 Correct 141 ms 98624 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 98452 KB Output is correct
2 Correct 45 ms 98400 KB Output is correct
3 Correct 185 ms 98676 KB Output is correct
4 Correct 190 ms 98704 KB Output is correct
5 Correct 197 ms 98692 KB Output is correct
6 Correct 198 ms 98764 KB Output is correct
7 Correct 278 ms 98844 KB Output is correct
8 Correct 258 ms 98748 KB Output is correct
9 Correct 141 ms 98624 KB Output is correct
10 Correct 43 ms 98452 KB Output is correct
11 Correct 43 ms 98432 KB Output is correct
12 Correct 181 ms 98636 KB Output is correct
13 Correct 187 ms 98652 KB Output is correct
14 Correct 178 ms 98780 KB Output is correct
15 Correct 194 ms 98764 KB Output is correct
16 Correct 277 ms 98656 KB Output is correct
17 Correct 266 ms 98760 KB Output is correct
18 Correct 152 ms 98556 KB Output is correct
19 Runtime error 281 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 44 ms 98452 KB Output is correct
2 Correct 45 ms 98400 KB Output is correct
3 Correct 185 ms 98676 KB Output is correct
4 Correct 190 ms 98704 KB Output is correct
5 Correct 197 ms 98692 KB Output is correct
6 Correct 198 ms 98764 KB Output is correct
7 Correct 278 ms 98844 KB Output is correct
8 Correct 258 ms 98748 KB Output is correct
9 Correct 141 ms 98624 KB Output is correct
10 Correct 54 ms 98376 KB Output is correct
11 Correct 57 ms 98376 KB Output is correct
12 Correct 200 ms 98628 KB Output is correct
13 Correct 203 ms 98636 KB Output is correct
14 Correct 226 ms 98676 KB Output is correct
15 Correct 231 ms 98628 KB Output is correct
16 Correct 299 ms 98616 KB Output is correct
17 Correct 263 ms 98724 KB Output is correct
18 Correct 151 ms 98508 KB Output is correct
19 Runtime error 338 ms 233680 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 282 ms 233660 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 44 ms 98516 KB Output is correct
2 Runtime error 272 ms 233916 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -