oj.uz

답안 #653596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653596 2022-10-27T11:26:21 Z AlperenT Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 52476 KB 
#include <bits/stdc++.h>

using namespace std;

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

int n, q, canmove[N][100 + 5];

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;

pair<int, int> query[N];

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

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

    cin >> n >> q;

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

    for(int i = 1; i <= q; i++){
        cin >> query[i].first >> query[i].second;
    }

    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());

    for(int i = 1; i <= q; i++){
        for(int j = 1; j <= n; j++){
            if(arr[query[i].first].r == arr[j].r){
                canmove[j][i] = 1;
            }
        }

        canmove[query[i].first][i] = 0;
    }

    for(int i = 1; i <= q; 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]);
        }
    }

    for(int i = 1; i <= q; i++){
        if(canmove[query[i].second][i] == INF) cout << "impossible\n";
        else cout << canmove[query[i].second][i] << "\n"; 
    }
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 44536 KB Output is correct
2 Execution timed out 1585 ms 52392 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 44540 KB Output is correct
2 Correct 160 ms 44540 KB Output is correct
3 Correct 223 ms 44624 KB Output is correct
4 Correct 199 ms 44508 KB Output is correct
5 Correct 137 ms 44620 KB Output is correct
6 Correct 175 ms 44544 KB Output is correct
7 Correct 217 ms 44748 KB Output is correct
8 Correct 159 ms 44668 KB Output is correct
9 Correct 151 ms 44572 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 44540 KB Output is correct
2 Correct 160 ms 44540 KB Output is correct
3 Correct 223 ms 44624 KB Output is correct
4 Correct 199 ms 44508 KB Output is correct
5 Correct 137 ms 44620 KB Output is correct
6 Correct 175 ms 44544 KB Output is correct
7 Correct 217 ms 44748 KB Output is correct
8 Correct 159 ms 44668 KB Output is correct
9 Correct 151 ms 44572 KB Output is correct
10 Correct 92 ms 44544 KB Output is correct
11 Correct 76 ms 44536 KB Output is correct
12 Correct 135 ms 44624 KB Output is correct
13 Correct 183 ms 44620 KB Output is correct
14 Correct 167 ms 44620 KB Output is correct
15 Correct 128 ms 44548 KB Output is correct
16 Correct 184 ms 44664 KB Output is correct
17 Correct 169 ms 44588 KB Output is correct
18 Correct 139 ms 44576 KB Output is correct
19 Execution timed out 1591 ms 45816 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 44540 KB Output is correct
2 Correct 160 ms 44540 KB Output is correct
3 Correct 223 ms 44624 KB Output is correct
4 Correct 199 ms 44508 KB Output is correct
5 Correct 137 ms 44620 KB Output is correct
6 Correct 175 ms 44544 KB Output is correct
7 Correct 217 ms 44748 KB Output is correct
8 Correct 159 ms 44668 KB Output is correct
9 Correct 151 ms 44572 KB Output is correct
10 Correct 57 ms 44536 KB Output is correct
11 Correct 58 ms 44540 KB Output is correct
12 Correct 133 ms 44540 KB Output is correct
13 Correct 154 ms 44536 KB Output is correct
14 Correct 132 ms 44552 KB Output is correct
15 Correct 144 ms 44544 KB Output is correct
16 Correct 160 ms 44548 KB Output is correct
17 Correct 154 ms 44664 KB Output is correct
18 Correct 150 ms 44544 KB Output is correct
19 Execution timed out 1586 ms 51672 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1586 ms 52476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 44536 KB Output is correct
2 Execution timed out 1585 ms 52392 KB Time limit exceeded
3 Halted 0 ms 0 KB -