oj.uz

Submission #653600

# Submission time Handle Problem Language Result Execution time Memory
653600 2022-10-27T11:30:57 Z AlperenT Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 52420 KB 
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx")

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

# Verdict Execution time Memory Grader output
1 Correct 19 ms 44500 KB Output is correct
2 Execution timed out 1596 ms 52368 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 44500 KB Output is correct
2 Correct 19 ms 44496 KB Output is correct
3 Correct 47 ms 44636 KB Output is correct
4 Correct 45 ms 44584 KB Output is correct
5 Correct 46 ms 44628 KB Output is correct
6 Correct 50 ms 44584 KB Output is correct
7 Correct 53 ms 44644 KB Output is correct
8 Correct 57 ms 44668 KB Output is correct
9 Correct 40 ms 44560 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 44500 KB Output is correct
2 Correct 19 ms 44496 KB Output is correct
3 Correct 47 ms 44636 KB Output is correct
4 Correct 45 ms 44584 KB Output is correct
5 Correct 46 ms 44628 KB Output is correct
6 Correct 50 ms 44584 KB Output is correct
7 Correct 53 ms 44644 KB Output is correct
8 Correct 57 ms 44668 KB Output is correct
9 Correct 40 ms 44560 KB Output is correct
10 Correct 19 ms 44512 KB Output is correct
11 Correct 19 ms 44508 KB Output is correct
12 Correct 42 ms 44528 KB Output is correct
13 Correct 44 ms 44608 KB Output is correct
14 Correct 43 ms 44628 KB Output is correct
15 Correct 45 ms 44624 KB Output is correct
16 Correct 54 ms 44668 KB Output is correct
17 Correct 51 ms 44604 KB Output is correct
18 Correct 38 ms 44580 KB Output is correct
19 Execution timed out 1597 ms 45792 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 44500 KB Output is correct
2 Correct 19 ms 44496 KB Output is correct
3 Correct 47 ms 44636 KB Output is correct
4 Correct 45 ms 44584 KB Output is correct
5 Correct 46 ms 44628 KB Output is correct
6 Correct 50 ms 44584 KB Output is correct
7 Correct 53 ms 44644 KB Output is correct
8 Correct 57 ms 44668 KB Output is correct
9 Correct 40 ms 44560 KB Output is correct
10 Correct 19 ms 44500 KB Output is correct
11 Correct 20 ms 44500 KB Output is correct
12 Correct 49 ms 44628 KB Output is correct
13 Correct 46 ms 44620 KB Output is correct
14 Correct 43 ms 44636 KB Output is correct
15 Correct 46 ms 44628 KB Output is correct
16 Correct 54 ms 44676 KB Output is correct
17 Correct 50 ms 44672 KB Output is correct
18 Correct 38 ms 44500 KB Output is correct
19 Execution timed out 1584 ms 51628 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1590 ms 52420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 44500 KB Output is correct
2 Execution timed out 1596 ms 52368 KB Time limit exceeded
3 Halted 0 ms 0 KB -