oj.uz

Submission #1002231

# Submission time Handle Problem Language Result Execution time Memory
1002231 2024-06-19T11:14:04 Z Andrey Event Hopping (BOI22_events) C++14
0 / 100
 81 ms 24980 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[l],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;
        if(a == b) {
            cout << ans << "\n";
            continue;
        }
        for(int j = 16; j >= 0; j--) {
            if(banana[b][j] == -1 || banana[b][j] < a) {
                continue;
            }
            ans+=(1 << j);
            b = banana[b][j];
        }
        if(b == a) {
            cout << ans << "\n";
        }
        else if(wow[b] <= bruh[a]) {
            cout << ans+1 << "\n";
        }
        else {
            cout << "impossible\n";
        }
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 70 ms 24392 KB Output is correct
3 Correct 58 ms 24404 KB Output is correct
4 Correct 62 ms 24400 KB Output is correct
5 Incorrect 57 ms 24980 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8024 KB Output is correct
6 Incorrect 2 ms 8028 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8024 KB Output is correct
6 Incorrect 2 ms 8028 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8024 KB Output is correct
6 Incorrect 2 ms 8028 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 24380 KB Output is correct
2 Correct 58 ms 24528 KB Output is correct
3 Correct 62 ms 24384 KB Output is correct
4 Correct 58 ms 24916 KB Output is correct
5 Correct 63 ms 24660 KB Output is correct
6 Incorrect 81 ms 24692 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 70 ms 24392 KB Output is correct
3 Correct 58 ms 24404 KB Output is correct
4 Correct 62 ms 24400 KB Output is correct
5 Incorrect 57 ms 24980 KB Output isn't correct
6 Halted 0 ms 0 KB -