oj.uz

Submission #1002185

# Submission time Handle Problem Language Result Execution time Memory
1002185 2024-06-19T10:47:23 Z Andrey Event Hopping (BOI22_events) C++14
30 / 100
 79 ms 25800 KB 
#include<bits/stdc++.h>
using namespace std;

vector<int> bruh(200001);
vector<int> wow(200001);
vector<pair<int,int>> seg(500001);

void build(int l, int r, int x) {
    if(l == r) {
        seg[x] = {wow[x],l};
        return;
    }
    int m = (l+r)/2;
    build(l,m,x*2);
    build(m+1,r,x*2+1);
    seg[x] = min(seg[x*2],seg[x*2+1]);
}

pair<int,int> calc(int l, int r, int x, int ql, int qr) {
    if(l == ql && r == qr) {
        return seg[x];
    }
    int m = (l+r)/2;
    if(qr <= m) {
        return calc(l,m,x*2,ql,qr);
    }
    else if(ql > m) {
        return calc(m+1,r,x*2+1,ql,qr);
    }
    else {
        return min(calc(l,m,x*2,ql,m),calc(m+1,r,x*2+1,m+1,qr));
    }
}

int apple[100001][17];
int banana[100001][17];

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,q,a,b;
    cin >> n >> q;
    vector<pair<pair<int,int>,int>> haha(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> a >> b;
        haha[i] = {{b,a},i};
    }
    sort(haha.begin(),haha.end());
    vector<int> pos(n+1);
    for(int i = 1; i <= n; i++) {
        pos[haha[i].second] = i;
        bruh[i] = haha[i].first.first;
        wow[i] = haha[i].first.second;
    }
    priority_queue<pair<int,int>> idk;
    for(int i = n; i >= 1; i--) {
        while(!idk.empty() && idk.top().second > bruh[i]) {
            idk.pop();
        }
        if(idk.empty()) {
            apple[i][0] = -1;
        }
        else {
            apple[i][0] = idk.top().first;
        }
        idk.push({i,wow[i]});
    }
    build(1,n,1);
    for(int i = 1; i <= n; i++) {
        int l,r;
        if(i == 1 || bruh[i-1] < wow[i]) {
            banana[i][0] = -1;
        }
        else{ 
            l = 1,r = i-1;
            while(l < r) {
                int m = (l+r)/2;
                if(bruh[l] < wow[i]) {
                    l = m+1;
                }
                else {
                    r = m;
                }
            }
            banana[i][0] = calc(1,n,1,l,i-1).second;
        }
    }
    for(int i = 1; i < 17; i++) {
        for(int j = 1; j <= n; j++) {
            if(apple[j][i-1] == -1) {
                apple[j][i] = -1;
            }
            else {
                apple[j][i] = apple[apple[j][i-1]][i-1];
            }
            if(banana[j][i-1] == -1) {
                banana[j][i] = -1;
            }
            else {
                banana[j][i] = banana[banana[j][i-1]][i-1];
            }
        }
    }
    for(int i = 0; i < q; i++) {
        cin >> a >> b;
        a = pos[a];
        b = pos[b];
        if(a > b) {
            if(bruh[a] == bruh[b]) {
                cout << 1 << "\n";
            }
            else {
                cout << "impossible\n";
            }
            continue;
        }
        int ans = 0;
        for(int j = 16; j >= 0; j--) {
            if(apple[a][j] == -1 || apple[a][j] > b) {
                continue;
            }
            ans+=(1 << j);
            a = apple[a][j];
        }
        if(a == b) {
            cout << ans << "\n";
            continue;
        }
        for(int j = 16; j >= 0; j--) {
            if(banana[b][j] == -1 || wow[banana[b][j]] <= bruh[a]) {
                continue;
            }
            ans+=(1 << j);
            b = banana[b][j];
        }
        if(banana[b][0] == -1 || banana[b][0] > bruh[a]) {
            cout << "impossible\n";
        }
        else {
            cout << ans+1 << "\n";
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 59 ms 24336 KB Output is correct
3 Correct 60 ms 24400 KB Output is correct
4 Correct 64 ms 24352 KB Output is correct
5 Correct 76 ms 24404 KB Output is correct
6 Correct 65 ms 24404 KB Output is correct
7 Correct 60 ms 24416 KB Output is correct
8 Correct 50 ms 25800 KB Output is correct
9 Correct 60 ms 24812 KB Output is correct
10 Correct 71 ms 24656 KB Output is correct
11 Correct 64 ms 24912 KB Output is correct
12 Correct 41 ms 24012 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 5980 KB Output is correct
4 Correct 4 ms 5980 KB Output is correct
5 Incorrect 3 ms 6080 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 5980 KB Output is correct
4 Correct 4 ms 5980 KB Output is correct
5 Incorrect 3 ms 6080 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 5980 KB Output is correct
4 Correct 4 ms 5980 KB Output is correct
5 Incorrect 3 ms 6080 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 24512 KB Output is correct
2 Correct 60 ms 24372 KB Output is correct
3 Correct 74 ms 24508 KB Output is correct
4 Correct 46 ms 24780 KB Output is correct
5 Correct 71 ms 24768 KB Output is correct
6 Correct 73 ms 24656 KB Output is correct
7 Correct 71 ms 24640 KB Output is correct
8 Correct 70 ms 24656 KB Output is correct
9 Correct 39 ms 23504 KB Output is correct
10 Correct 79 ms 24148 KB Output is correct
11 Correct 65 ms 24272 KB Output is correct
12 Correct 64 ms 24148 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 59 ms 24336 KB Output is correct
3 Correct 60 ms 24400 KB Output is correct
4 Correct 64 ms 24352 KB Output is correct
5 Correct 76 ms 24404 KB Output is correct
6 Correct 65 ms 24404 KB Output is correct
7 Correct 60 ms 24416 KB Output is correct
8 Correct 50 ms 25800 KB Output is correct
9 Correct 60 ms 24812 KB Output is correct
10 Correct 71 ms 24656 KB Output is correct
11 Correct 64 ms 24912 KB Output is correct
12 Correct 41 ms 24012 KB Output is correct
13 Correct 4 ms 5720 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 3 ms 5980 KB Output is correct
16 Correct 4 ms 5980 KB Output is correct
17 Incorrect 3 ms 6080 KB Output isn't correct
18 Halted 0 ms 0 KB -