oj.uz

Submission #1002253

# Submission time Handle Problem Language Result Execution time Memory
1002253 2024-06-19T11:32:15 Z Andrey Event Hopping (BOI22_events) C++14
10 / 100
 72 ms 25548 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 = 1; i <= n; i++) {
        if(banana[i][0] != -1 && bruh[banana[i][0]] < wow[i]) {
            cout << 1/0;
        }
    }
    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 || 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;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:108:22: warning: division by zero [-Wdiv-by-zero]
  108 |             cout << 1/0;
      |                     ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7768 KB Output is correct
2 Correct 67 ms 24264 KB Output is correct
3 Correct 59 ms 24144 KB Output is correct
4 Correct 71 ms 24016 KB Output is correct
5 Correct 61 ms 24136 KB Output is correct
6 Correct 61 ms 24220 KB Output is correct
7 Correct 59 ms 24148 KB Output is correct
8 Correct 46 ms 25548 KB Output is correct
9 Correct 52 ms 24652 KB Output is correct
10 Correct 63 ms 24404 KB Output is correct
11 Correct 72 ms 24660 KB Output is correct
12 Correct 43 ms 24020 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 24148 KB Output is correct
2 Correct 64 ms 24368 KB Output is correct
3 Correct 63 ms 24400 KB Output is correct
4 Correct 47 ms 24912 KB Output is correct
5 Correct 68 ms 24912 KB Output is correct
6 Incorrect 67 ms 24400 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7768 KB Output is correct
2 Correct 67 ms 24264 KB Output is correct
3 Correct 59 ms 24144 KB Output is correct
4 Correct 71 ms 24016 KB Output is correct
5 Correct 61 ms 24136 KB Output is correct
6 Correct 61 ms 24220 KB Output is correct
7 Correct 59 ms 24148 KB Output is correct
8 Correct 46 ms 25548 KB Output is correct
9 Correct 52 ms 24652 KB Output is correct
10 Correct 63 ms 24404 KB Output is correct
11 Correct 72 ms 24660 KB Output is correct
12 Correct 43 ms 24020 KB Output is correct
13 Correct 2 ms 7768 KB Output is correct
14 Correct 2 ms 7768 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 3 ms 8028 KB Output is correct
17 Incorrect 2 ms 8024 KB Output isn't correct
18 Halted 0 ms 0 KB -