oj.uz

Submission #653595

# Submission time Handle Problem Language Result Execution time Memory
653595 2022-10-27T11:23:34 Z AlperenT Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 62940 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());

    map<int, vector<int>> mp;

    for(int i = 1; i <= n; i++) mp[arr[i].r].push_back(i);

    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][query[i].first] = min(canmove[p.second][query[i].first], sgt.query(p.first.l, p.first.r) + 1);

            sgt.update(p.first.r, canmove[p.second][query[i].first]);
        }
    }

    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 64 ms 44500 KB Output is correct
2 Execution timed out 1581 ms 62940 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 44500 KB Output is correct
2 Correct 69 ms 44540 KB Output is correct
3 Incorrect 110 ms 44692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 44500 KB Output is correct
2 Correct 69 ms 44540 KB Output is correct
3 Incorrect 110 ms 44692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 44500 KB Output is correct
2 Correct 69 ms 44540 KB Output is correct
3 Incorrect 110 ms 44692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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