oj.uz

Submission #777052

# Submission time Handle Problem Language Result Execution time Memory
777052 2023-07-08T14:54:02 Z Cookie Event Hopping (BOI22_events) C++14
20 / 100
 71 ms 13240 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;
int pos[mxn + 1], up[mxn + 1][18];
vt<th>comp;
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        int s, e; cin >> s >> e;
        comp.pb({s, e, i});
    }
    sort(comp.begin(), comp.end());
    int lp = 0;
    for(int i = 0; i < sz(comp); i++){
        pos[comp[i].id] = i;
        while(lp < sz(comp) && comp[lp].s <= comp[i].e)lp++;
        up[i][0] = lp - 1;
    }
    for(int i = 1; i < 18; i++){
        for(int j = 0; j < sz(comp); j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    for(int i = 0; i < q; i++){
        int s, e; cin >> s >> e; 
        s = pos[s]; e = pos[e];
        
        if(s > e){
            cout << "impossible" << "\n";
            continue;
        }else if(s == e){
            cout << 0 << "\n";
            continue;
        }
        int ans = 0;
        for(int i = 17; i >= 0; i--){
            if(up[s][i] < e){
                s = up[s][i]; ans += (1 << i);
            }
        }
        if(up[s][0] < e){
            cout << "impossible" << "\n";
        }else{
            cout << ans + 1 << "\n";
        }
    }
    return(0);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9672 KB Output is correct
2 Correct 59 ms 12672 KB Output is correct
3 Correct 53 ms 12736 KB Output is correct
4 Correct 55 ms 13240 KB Output is correct
5 Correct 71 ms 13092 KB Output is correct
6 Correct 59 ms 12868 KB Output is correct
7 Correct 55 ms 12864 KB Output is correct
8 Correct 53 ms 12992 KB Output is correct
9 Correct 35 ms 10948 KB Output is correct
10 Correct 57 ms 12440 KB Output is correct
11 Correct 48 ms 12352 KB Output is correct
12 Correct 49 ms 12468 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -