oj.uz

Submission #1002251

# Submission time Handle Problem Language Result Execution time Memory
1002251 2024-06-19T11:30:15 Z Andrey Event Hopping (BOI22_events) C++14
30 / 100
 77 ms 24528 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 2 ms 7772 KB Output is correct
2 Correct 57 ms 22976 KB Output is correct
3 Correct 58 ms 23088 KB Output is correct
4 Correct 61 ms 23144 KB Output is correct
5 Correct 64 ms 23128 KB Output is correct
6 Correct 56 ms 23132 KB Output is correct
7 Correct 61 ms 23244 KB Output is correct
8 Correct 45 ms 24528 KB Output is correct
9 Correct 46 ms 23632 KB Output is correct
10 Correct 77 ms 23380 KB Output is correct
11 Correct 61 ms 23520 KB Output is correct
12 Correct 47 ms 23380 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 2 ms 7792 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Incorrect 2 ms 7992 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 7772 KB Output is correct
2 Correct 2 ms 7792 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Incorrect 2 ms 7992 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 7772 KB Output is correct
2 Correct 2 ms 7792 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Incorrect 2 ms 7992 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 54 ms 23152 KB Output is correct
2 Correct 53 ms 23124 KB Output is correct
3 Correct 62 ms 23024 KB Output is correct
4 Correct 52 ms 23632 KB Output is correct
5 Correct 56 ms 23376 KB Output is correct
6 Correct 70 ms 23236 KB Output is correct
7 Correct 65 ms 23124 KB Output is correct
8 Correct 60 ms 23380 KB Output is correct
9 Correct 35 ms 23076 KB Output is correct
10 Correct 61 ms 22864 KB Output is correct
11 Correct 74 ms 23000 KB Output is correct
12 Correct 54 ms 22932 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 57 ms 22976 KB Output is correct
3 Correct 58 ms 23088 KB Output is correct
4 Correct 61 ms 23144 KB Output is correct
5 Correct 64 ms 23128 KB Output is correct
6 Correct 56 ms 23132 KB Output is correct
7 Correct 61 ms 23244 KB Output is correct
8 Correct 45 ms 24528 KB Output is correct
9 Correct 46 ms 23632 KB Output is correct
10 Correct 77 ms 23380 KB Output is correct
11 Correct 61 ms 23520 KB Output is correct
12 Correct 47 ms 23380 KB Output is correct
13 Correct 2 ms 7772 KB Output is correct
14 Correct 2 ms 7792 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Incorrect 2 ms 7992 KB Output isn't correct
18 Halted 0 ms 0 KB -