oj.uz

Submission #656548

# Submission time Handle Problem Language Result Execution time Memory
656548 2022-11-08T00:33:51 Z Lobo Event Hopping (BOI22_events) C++17
25 / 100
 1500 ms 6196 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 1e5+10;

int n, q, idord[maxn], lf[maxn], rg[maxn], nx[maxn][25], pv[maxn][25];

void solve() {
    cin >> n >> q;
    vector<pair<pair<int,int>,int>> ord;
    for(int i = 1; i <= n; i++) {
        int l, r; cin >> l >> r;
        ord.pb(mp(mp(r,l),i));
    }
    // sort(all(ord));
    for(int i = 1; i <= n; i++) {
        idord[ord[i-1].sc] = i;
        lf[i] = ord[i-1].fr.sc;
        rg[i] = ord[i-1].fr.fr;
    }

    for(int i = 1; i <= n; i++) {
        nx[i][0] = 0;
        for(int j = 1; j <= n; j++) {
            if(j == i || !(lf[j] <= rg[i] && rg[i] <= rg[j]) || !(rg[j] > rg[i])) continue;
            if(nx[i][0] == 0 || rg[j] > rg[nx[i][0]]) nx[i][0] = j;
        }
        pv[i][0] = 0;
        for(int j = 1; j <= n; j++) {
            if(j == i || !(lf[i] <= rg[j] && rg[j] <= rg[i]) || !(lf[j] < lf[i])) continue;
            if(pv[i][0] == 0 || lf[j] < lf[pv[i][0]]) pv[i][0] = j;
        }
        // int l = i+1;
        // int r = n;
        // while(l <= r) {
        //     int mid = (l+r)/2;
        //     if(lf[mid] <= rg[i]) {
        //         nx[i][0] = mid;
        //         l = mid+1;
        //     }
        //     else {
        //         r = mid-1;
        //     }
        // }

        // cout << i << " " << nx[i][0] << " " << pv[i][0] << endl;
    }

    for(int j = 1; j <= 20; j++) {
        for(int i = 1; i <= n; i++) {
            nx[i][j] = nx[nx[i][j-1]][j-1];
            pv[i][j] = pv[pv[i][j-1]][j-1];
        }
    }

    while(q--) {
        int s,e; cin >> s >> e;
        s = idord[s];
        e = idord[e];

        int ans = 0;
        for(int j = 20; j >= 0; j--) {
            if(nx[s][j] != 0 && rg[nx[s][j]] < rg[e]) {
                ans+= (1<<j);
                s = nx[s][j];
            }
        }
        for(int j = 20; j >= 0; j--) {
            if(pv[e][j] != 0 && lf[pv[e][j]] > lf[s]) {
                ans+= (1<<j);
                e = pv[e][j];
            }
        }
        if(s == e) {
            cout << ans << endl;
        }
        else if(lf[e] <= rg[s] && rg[s] <= rg[e]) {
            cout << ans+1 << endl;
        }
        else if(nx[s][0] != 0 && lf[e] <= rg[nx[s][0]] && rg[nx[s][0]] <= rg[e]) {
            cout << ans+2 << endl;
        }
        else if(pv[e][0] != 0 && lf[pv[e][0]] <= rg[s] && rg[s] <= rg[pv[e][0]]) {
            cout << ans+2 << endl;
        }
        else {
            cout << "impossible" << endl;
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1570 ms 6100 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 7 ms 724 KB Output is correct
4 Correct 7 ms 724 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 8 ms 724 KB Output is correct
7 Correct 10 ms 724 KB Output is correct
8 Correct 8 ms 852 KB Output is correct
9 Correct 3 ms 724 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 7 ms 724 KB Output is correct
4 Correct 7 ms 724 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 8 ms 724 KB Output is correct
7 Correct 10 ms 724 KB Output is correct
8 Correct 8 ms 852 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 6 ms 724 KB Output is correct
13 Correct 6 ms 764 KB Output is correct
14 Correct 7 ms 724 KB Output is correct
15 Correct 9 ms 760 KB Output is correct
16 Correct 11 ms 856 KB Output is correct
17 Correct 8 ms 724 KB Output is correct
18 Correct 3 ms 724 KB Output is correct
19 Correct 237 ms 3288 KB Output is correct
20 Correct 189 ms 4220 KB Output is correct
21 Correct 199 ms 4352 KB Output is correct
22 Correct 232 ms 4464 KB Output is correct
23 Correct 272 ms 4432 KB Output is correct
24 Correct 211 ms 4252 KB Output is correct
25 Correct 207 ms 3984 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 7 ms 724 KB Output is correct
4 Correct 7 ms 724 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 8 ms 724 KB Output is correct
7 Correct 10 ms 724 KB Output is correct
8 Correct 8 ms 852 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 6 ms 732 KB Output is correct
13 Correct 6 ms 724 KB Output is correct
14 Correct 7 ms 724 KB Output is correct
15 Correct 8 ms 844 KB Output is correct
16 Correct 10 ms 732 KB Output is correct
17 Correct 8 ms 728 KB Output is correct
18 Correct 3 ms 724 KB Output is correct
19 Execution timed out 1540 ms 6196 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 1565 ms 6076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1570 ms 6100 KB Time limit exceeded
3 Halted 0 ms 0 KB -