oj.uz

Submission #777282

# Submission time Handle Problem Language Result Execution time Memory
777282 2023-07-09T01:43:13 Z Cookie Event Hopping (BOI22_events) C++14
25 / 100
 47 ms 32824 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 1e5 + 5, mxm = 1e5, sq = 400;
const int base = (1 << 18);
const ll inf = 1e9;
const ld pre = 1e-6;
struct th{
    int s, e, id;
    bool operator <(const th &b){
        return(s < b.s);
    }
};
int n, q;
vt<int>comp;
int find(int x){
    return(lower_bound(comp.begin(), comp.end(), x) - comp.begin());
}
pii up[mxn + 1][17];
int pref[mxn + 1][17], s[mxn + 1], e[mxn + 1];
pii get(int l, int r){
    int lg = __lg(r - l + 1);
    return(min(up[l][lg], up[r - (1 << lg) + 1][lg]));
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> s[i] >> e[i];
        comp.pb(s[i]); comp.pb(e[i]); 
    }
    sort(comp.begin(), comp.end());
    for(int i = 0; i < sz(comp); i++){
        up[i][0] = make_pair(inf, 0);
    }
    for(int i = 1; i <= n; i++){
        up[find(e[i])][0] = min(up[find(e[i])][0], make_pair(s[i], i));
    }
    for(int i = 1; i < 17; i++){
        for(int j = 0; j + (1 << i) - 1 < sz(comp); j++){
            up[j][i] = min(up[j][i - 1], up[j + (1 << (i - 1))][i - 1]);
        }
    }
    for(int i = 1; i <= n; i++){
        pref[i][0] = get(find(s[i]), find(e[i])).se;
        
    }
    for(int i = 1; i < 17; i++){
        for(int j = 1; j <= n; j++){
            pref[j][i] = pref[pref[j][i - 1]][i - 1];
        }
    }
    for(int i = 0; i < q; i++){
        int l, r; cin >> l >> r;
        if(l == r){
            cout << 0 << "\n";
        }else if(s[r] <= e[l]){
            if(e[r] >= e[l]){
                cout << 1 << "\n";
            }else{
                cout << "impossible" << "\n";
            }
        }else{
            int ans = 0;
            for(int i = 16; i >= 0; i--){
                int id = pref[r][i];
                
                if(s[id] > e[l]){
                    ans += (1 << i); r = pref[r][i];
                }
            }
            
            r = pref[r][0];
            
            if(s[r] <= e[l] && e[r] >= e[l]){
                cout << ans + 2 << "\n";
            }else{
                cout << "impossible" << "\n";
            }
        }
        
    }
    return(0);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 45 ms 30848 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 628 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 732 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 1 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 1 ms 732 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 2 ms 740 KB Output is correct
17 Correct 1 ms 724 KB Output is correct
18 Correct 1 ms 724 KB Output is correct
19 Correct 28 ms 3532 KB Output is correct
20 Correct 25 ms 3660 KB Output is correct
21 Correct 35 ms 3816 KB Output is correct
22 Correct 23 ms 3936 KB Output is correct
23 Correct 22 ms 3800 KB Output is correct
24 Correct 21 ms 3800 KB Output is correct
25 Correct 24 ms 3428 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 628 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 732 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 728 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 1 ms 736 KB Output is correct
17 Correct 1 ms 724 KB Output is correct
18 Correct 1 ms 724 KB Output is correct
19 Runtime error 45 ms 32824 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 30836 KB Execution killed with signal 11
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 Runtime error 45 ms 30848 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -