oj.uz

답안 #653587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653587 2022-10-27T11:06:35 Z AlperenT Event Hopping (BOI22_events) C++17
10 / 100
 321 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);
    }

    void reset(){
        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]);
        }
    }
};

SegTree sgt;

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++){
        sgt.reset();

        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

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 98416 KB Output is correct
2 Runtime error 276 ms 233756 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 98380 KB Output is correct
2 Correct 45 ms 98424 KB Output is correct
3 Correct 188 ms 98680 KB Output is correct
4 Correct 206 ms 98760 KB Output is correct
5 Correct 186 ms 98676 KB Output is correct
6 Correct 212 ms 98628 KB Output is correct
7 Correct 300 ms 98788 KB Output is correct
8 Correct 270 ms 98760 KB Output is correct
9 Correct 165 ms 98536 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 98380 KB Output is correct
2 Correct 45 ms 98424 KB Output is correct
3 Correct 188 ms 98680 KB Output is correct
4 Correct 206 ms 98760 KB Output is correct
5 Correct 186 ms 98676 KB Output is correct
6 Correct 212 ms 98628 KB Output is correct
7 Correct 300 ms 98788 KB Output is correct
8 Correct 270 ms 98760 KB Output is correct
9 Correct 165 ms 98536 KB Output is correct
10 Correct 52 ms 98380 KB Output is correct
11 Correct 45 ms 98392 KB Output is correct
12 Correct 190 ms 98680 KB Output is correct
13 Correct 203 ms 98676 KB Output is correct
14 Correct 214 ms 98680 KB Output is correct
15 Correct 207 ms 98508 KB Output is correct
16 Correct 288 ms 98728 KB Output is correct
17 Correct 281 ms 98728 KB Output is correct
18 Correct 151 ms 98540 KB Output is correct
19 Runtime error 256 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 98380 KB Output is correct
2 Correct 45 ms 98424 KB Output is correct
3 Correct 188 ms 98680 KB Output is correct
4 Correct 206 ms 98760 KB Output is correct
5 Correct 186 ms 98676 KB Output is correct
6 Correct 212 ms 98628 KB Output is correct
7 Correct 300 ms 98788 KB Output is correct
8 Correct 270 ms 98760 KB Output is correct
9 Correct 165 ms 98536 KB Output is correct
10 Correct 50 ms 98492 KB Output is correct
11 Correct 44 ms 98376 KB Output is correct
12 Correct 186 ms 98684 KB Output is correct
13 Correct 199 ms 98680 KB Output is correct
14 Correct 196 ms 98740 KB Output is correct
15 Correct 202 ms 98508 KB Output is correct
16 Correct 289 ms 98732 KB Output is correct
17 Correct 272 ms 98732 KB Output is correct
18 Correct 150 ms 98568 KB Output is correct
19 Runtime error 295 ms 233740 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 321 ms 233700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 98416 KB Output is correct
2 Runtime error 276 ms 233756 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -