oj.uz

답안 #653589

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653589 2022-10-27T11:08:25 Z AlperenT Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 233788 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 = 2 * 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 = 2 * 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 53 ms 98480 KB Output is correct
2 Runtime error 301 ms 233788 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 98380 KB Output is correct
2 Correct 44 ms 98472 KB Output is correct
3 Correct 214 ms 98840 KB Output is correct
4 Correct 211 ms 98680 KB Output is correct
5 Correct 200 ms 98680 KB Output is correct
6 Correct 221 ms 98632 KB Output is correct
7 Correct 296 ms 98732 KB Output is correct
8 Correct 274 ms 98728 KB Output is correct
9 Correct 160 ms 98540 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 98380 KB Output is correct
2 Correct 44 ms 98472 KB Output is correct
3 Correct 214 ms 98840 KB Output is correct
4 Correct 211 ms 98680 KB Output is correct
5 Correct 200 ms 98680 KB Output is correct
6 Correct 221 ms 98632 KB Output is correct
7 Correct 296 ms 98732 KB Output is correct
8 Correct 274 ms 98728 KB Output is correct
9 Correct 160 ms 98540 KB Output is correct
10 Correct 43 ms 98380 KB Output is correct
11 Correct 42 ms 98464 KB Output is correct
12 Correct 197 ms 98700 KB Output is correct
13 Correct 201 ms 98764 KB Output is correct
14 Correct 198 ms 98684 KB Output is correct
15 Correct 217 ms 98756 KB Output is correct
16 Correct 301 ms 98732 KB Output is correct
17 Correct 274 ms 98728 KB Output is correct
18 Correct 158 ms 98608 KB Output is correct
19 Execution timed out 1587 ms 99660 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 98380 KB Output is correct
2 Correct 44 ms 98472 KB Output is correct
3 Correct 214 ms 98840 KB Output is correct
4 Correct 211 ms 98680 KB Output is correct
5 Correct 200 ms 98680 KB Output is correct
6 Correct 221 ms 98632 KB Output is correct
7 Correct 296 ms 98732 KB Output is correct
8 Correct 274 ms 98728 KB Output is correct
9 Correct 160 ms 98540 KB Output is correct
10 Correct 46 ms 98444 KB Output is correct
11 Correct 45 ms 98380 KB Output is correct
12 Correct 206 ms 98684 KB Output is correct
13 Correct 202 ms 98680 KB Output is correct
14 Correct 202 ms 98680 KB Output is correct
15 Correct 221 ms 98636 KB Output is correct
16 Correct 297 ms 98628 KB Output is correct
17 Correct 279 ms 98636 KB Output is correct
18 Correct 156 ms 98544 KB Output is correct
19 Runtime error 273 ms 233660 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 98480 KB Output is correct
2 Runtime error 301 ms 233788 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -