oj.uz

Submission #653609

# Submission time Handle Problem Language Result Execution time Memory
653609 2022-10-27T11:37:10 Z AlperenT Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 52436 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], vals[N * 2];

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 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 min(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] = val;
            vals[pos] = 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] = min(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++){
        fill(vals, vals + N * 2, INF);
        
        sgt.reset();

        for(auto p : v){
            canmove[p.second][i] = min(canmove[p.second][i], sgt.query(p.first.l, p.first.r) + 1);

            if(canmove[p.second][i] < vals[p.first.r]) 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 25 ms 45268 KB Output is correct
2 Execution timed out 1575 ms 52436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45268 KB Output is correct
2 Correct 22 ms 45268 KB Output is correct
3 Correct 62 ms 45356 KB Output is correct
4 Correct 46 ms 45408 KB Output is correct
5 Correct 45 ms 45388 KB Output is correct
6 Correct 51 ms 45408 KB Output is correct
7 Correct 64 ms 45444 KB Output is correct
8 Correct 53 ms 45376 KB Output is correct
9 Correct 42 ms 45248 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45268 KB Output is correct
2 Correct 22 ms 45268 KB Output is correct
3 Correct 62 ms 45356 KB Output is correct
4 Correct 46 ms 45408 KB Output is correct
5 Correct 45 ms 45388 KB Output is correct
6 Correct 51 ms 45408 KB Output is correct
7 Correct 64 ms 45444 KB Output is correct
8 Correct 53 ms 45376 KB Output is correct
9 Correct 42 ms 45248 KB Output is correct
10 Correct 20 ms 45268 KB Output is correct
11 Correct 23 ms 45328 KB Output is correct
12 Correct 62 ms 45372 KB Output is correct
13 Correct 44 ms 45396 KB Output is correct
14 Correct 51 ms 45400 KB Output is correct
15 Correct 44 ms 45408 KB Output is correct
16 Correct 56 ms 45336 KB Output is correct
17 Correct 59 ms 45448 KB Output is correct
18 Correct 42 ms 45244 KB Output is correct
19 Execution timed out 1579 ms 46648 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45268 KB Output is correct
2 Correct 22 ms 45268 KB Output is correct
3 Correct 62 ms 45356 KB Output is correct
4 Correct 46 ms 45408 KB Output is correct
5 Correct 45 ms 45388 KB Output is correct
6 Correct 51 ms 45408 KB Output is correct
7 Correct 64 ms 45444 KB Output is correct
8 Correct 53 ms 45376 KB Output is correct
9 Correct 42 ms 45248 KB Output is correct
10 Correct 19 ms 45340 KB Output is correct
11 Correct 23 ms 45260 KB Output is correct
12 Correct 54 ms 45404 KB Output is correct
13 Correct 48 ms 45400 KB Output is correct
14 Correct 54 ms 45408 KB Output is correct
15 Correct 46 ms 45396 KB Output is correct
16 Correct 61 ms 45464 KB Output is correct
17 Correct 53 ms 45376 KB Output is correct
18 Correct 41 ms 45288 KB Output is correct
19 Execution timed out 1588 ms 52108 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 1523 ms 52408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 45268 KB Output is correct
2 Execution timed out 1575 ms 52436 KB Time limit exceeded
3 Halted 0 ms 0 KB -