oj.uz

Submission #529489

# Submission time Handle Problem Language Result Execution time Memory
529489 2022-02-23T04:41:17 Z wiwiho Railway Trip 2 (JOI22_ho_t4) C++14
0 / 100
 479 ms 27388 KB 
#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define mp make_pair
#define F first
#define S second
#define eb emplace_back
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())

using namespace std;

typedef long long ll;
typedef double ld;

using pii = pair<int, int>;

ll iceil(ll a, ll b){
    return (a + b - 1) / b;
}

#define lc (2 * id + 1)
#define rc (2 * id + 2)

int n;

struct Node{
    pii mx = mp(-1, -1), tag = mp(-1, -1);
};

vector<Node> st;

void addtag(int id, pii v){
    st[id].tag = max(st[id].tag, v);
    st[id].mx = max(st[id].mx, v);
}

void push(int id){
    addtag(lc, st[id].tag);
    addtag(rc, st[id].tag);
    st[id].tag = mp(-1, -1);
}

void pull(int id){
    st[id].mx = max(st[lc].mx, st[rc].mx);
}

void modify(int l, int r, pii v, int L = 1, int R = n, int id = 0){
    if(l <= L && R <= r){
        addtag(id, v);
        return;
    }
    push(id);
    int M = (L + R) / 2;
    if(r <= M) modify(l, r, v, L, M, lc);
    else if(l > M) modify(l, r, v, M + 1, R, rc);
    else{
        modify(l, r, v, L, M, lc);
        modify(l, r, v, M + 1, R, rc);
    }
    pull(id);
}

pii query(int l, int r, int L = 1, int R = n, int id = 0){
    if(l <= L && R <= r) return st[id].mx;
    push(id);
    int M = (L + R) / 2;
    if(r <= M) return query(l, r, L, M, lc);
    else if(l > M) return query(l, r, M + 1, R, rc);
    else return max(query(l, r, L, M, lc), query(l, r, M + 1, R, rc));
}

vector<vector<int>> anc;
vector<int> lb, rb;
int ts = 0;

const int SZ = 20;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int K, m;
    cin >> n >> K >> m;
    rb.resize(m + 1);
    anc.resize(SZ, vector<int>(m + 1));
    lb.resize(m + 1);
    rb.resize(m + 1);
    st.resize(4 * n);

    for(int i = 1; i <= m; i++) anc[0][i] = i;

    for(int i = 1; i <= m; i++){
        int l, r;
        cin >> l >> r;
        lb[i] = l; rb[i] = r;
        modify(l, min(r - 1, l + K - 1), mp(r, i));
    }

    vector<int> best(n + 1);
    for(int i = 1; i <= n; i++){
        best[i] = query(i, i).S;
    }

    for(int i = 1; i <= m; i++){
        int pr = query(lb[i], rb[i]).S;
        if(pr == -1) continue;
        //cerr << "pr " << i << " " << pr << "\n";
        anc[0][i] = pr;
    }

    for(int i = 1; i < SZ; i++){
        for(int j = 1; j <= m; j++){
            anc[i][j] = anc[i - 1][anc[i - 1][j]];
        }
    }

    int q;
    cin >> q;
    
    while(q--){

        int s, t;
        cin >> s >> t;
        
        int now = best[s];
        if(now == -1){
            cout << "-1\n";
            continue;
        }

        if(rb[now] >= t){
            cout << "1\n";
            continue;
        }

        int ans = 1;
        for(int i = SZ - 1; i >= 0; i--){
            if(rb[anc[i][now]] < t){
                now = anc[i][now];
                ans += 1 << i;
            }
        }
        now = anc[0][now];
        ans++;
        if(rb[now] < t){
            cout << "-1\n";
            continue;
        }
        cout << ans << "\n";

    }

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 27388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 27104 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 24352 KB Output is correct
2 Correct 233 ms 15856 KB Output is correct
3 Correct 124 ms 11540 KB Output is correct
4 Correct 82 ms 8940 KB Output is correct
5 Correct 52 ms 7524 KB Output is correct
6 Correct 55 ms 7196 KB Output is correct
7 Correct 182 ms 15612 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 6 ms 588 KB Output is correct
10 Correct 394 ms 24236 KB Output is correct
11 Correct 387 ms 24244 KB Output is correct
12 Correct 442 ms 24172 KB Output is correct
13 Correct 457 ms 24152 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Incorrect 3 ms 588 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -