oj.uz

Submission #528190

# Submission time Handle Problem Language Result Execution time Memory
528190 2022-02-19T16:25:44 Z doowey Railway Trip 2 (JOI22_ho_t4) C++14
16 / 100
 556 ms 71720 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 1;
const int LOG = 18;
int L[LOG][N];
int R[LOG][N];
multiset<int> add[N];
multiset<int> del[N];

int A[N];
int B[N];

pii segt[LOG][N * 4 + 512];

void build(int dep, int node, int lef, int rig){
    if(lef == rig){
        segt[dep][node] = mp(L[dep][lef], R[dep][rig]);
        return;
    }
    int mid = (lef + rig) / 2;
    build(dep, node * 2, lef, mid);
    build(dep, node * 2 + 1, mid + 1, rig);
    segt[dep][node].fi = min(segt[dep][node*2].fi, segt[dep][node*2+1].fi);
    segt[dep][node].se = max(segt[dep][node*2].se, segt[dep][node*2+1].se);
}

pii get(int dep, int node, int cl, int cr, int tl, int tr){
    if(cr < tl || cl > tr){
        return mp((int)1e9,-1);
    }
    if(cl >= tl && cr <= tr){
        return segt[dep][node];
    }
    int mid = (cl + cr) / 2;
    pii A = get(dep, node * 2, cl, mid, tl, tr);
    pii B = get(dep, node * 2 + 1, mid + 1, cr, tl, tr);
    return mp(min(A.fi, B.fi), max(A.se, B.se));
}


int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n, k;
    cin >> n >> k;
    int m;
    cin >> m;
    int seg;
    for(int id = 1; id <= m ;id ++ ){
        cin >> A[id] >> B[id];
        if(A[id] < B[id]){
            seg = min(B[id], A[id] + k - 1);
            add[A[id]].insert(B[id]);
            del[seg + 1].insert(B[id]);
        }
        else{
            seg = max(A[id] - k + 1, B[id]);
            add[seg].insert(B[id]);
            del[A[id] + 1].insert(B[id]);
        }
    }
    multiset<int> pp;
    int low;
    for(int iq = 1; iq <= n; iq ++ ){
        for(auto x : add[iq]){
            pp.insert(x);
        }
        for(auto x : del[iq]){
            pp.erase(pp.find(x));
        }
        L[0][iq] = R[0][iq] = iq;
        if(!pp.empty()){
            auto it = pp.begin();
            L[0][iq] = min(L[0][iq], *it);
            it = pp.end();
            it -- ;
            R[0][iq] = max(R[0][iq], *it);
        }
    }
    pii F;
    for(int c = 1; c < LOG; c ++ ){
        build(c - 1, 1, 1, n);
        for(int iq = 1; iq <= n; iq ++ ){
            F = get(c - 1, 1, 1, n, L[c-1][iq], R[c-1][iq]);
            L[c][iq] = F.fi;
            R[c][iq] = F.se;
        }
    }
    build(LOG - 1, 1, 1, n);
    int q;
    cin >> q;
    int s, t;
    int lef, rig;
    int dep;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> s >> t;
        lef = rig = s;
        dep = 0;
        for(int lg = LOG - 1; lg >= 0 ; lg -- ){
            F = get(lg, 1, 1, n, lef, rig);
            if(t < F.fi || t > F.se){
                lef = F.fi;
                rig = F.se;
                dep += (1 << lg);
            }
        }
        F = get(0, 1, 1, n, lef, rig);
        if(F.fi <= t && t <= F.se){
            cout << dep + 1 << "\n";
        }
        else{
            cout << -1 << "\n";
        }
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:73:9: warning: unused variable 'low' [-Wunused-variable]
   73 |     int low;
      |         ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10188 KB Output is correct
2 Correct 7 ms 10252 KB Output is correct
3 Correct 5 ms 10188 KB Output is correct
4 Correct 6 ms 10188 KB Output is correct
5 Correct 7 ms 10188 KB Output is correct
6 Correct 6 ms 10188 KB Output is correct
7 Correct 6 ms 10188 KB Output is correct
8 Correct 6 ms 10196 KB Output is correct
9 Correct 6 ms 10188 KB Output is correct
10 Correct 5 ms 9932 KB Output is correct
11 Correct 7 ms 10204 KB Output is correct
12 Correct 6 ms 10200 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10188 KB Output is correct
2 Correct 7 ms 10252 KB Output is correct
3 Correct 5 ms 10188 KB Output is correct
4 Correct 6 ms 10188 KB Output is correct
5 Correct 7 ms 10188 KB Output is correct
6 Correct 6 ms 10188 KB Output is correct
7 Correct 6 ms 10188 KB Output is correct
8 Correct 6 ms 10196 KB Output is correct
9 Correct 6 ms 10188 KB Output is correct
10 Correct 5 ms 9932 KB Output is correct
11 Correct 7 ms 10204 KB Output is correct
12 Correct 6 ms 10200 KB Output is correct
13 Correct 17 ms 11044 KB Output is correct
14 Correct 15 ms 11048 KB Output is correct
15 Correct 10 ms 10988 KB Output is correct
16 Correct 11 ms 11084 KB Output is correct
17 Correct 14 ms 11084 KB Output is correct
18 Correct 10 ms 11084 KB Output is correct
19 Correct 13 ms 11128 KB Output is correct
20 Correct 10 ms 11124 KB Output is correct
21 Correct 8 ms 11048 KB Output is correct
22 Correct 13 ms 11144 KB Output is correct
23 Correct 13 ms 11084 KB Output is correct
24 Correct 15 ms 11040 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 69072 KB Output is correct
2 Correct 415 ms 68924 KB Output is correct
3 Correct 495 ms 70552 KB Output is correct
4 Correct 392 ms 68360 KB Output is correct
5 Runtime error 101 ms 43052 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 71720 KB Output is correct
2 Runtime error 90 ms 41284 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10188 KB Output is correct
2 Correct 7 ms 10252 KB Output is correct
3 Correct 5 ms 10188 KB Output is correct
4 Correct 6 ms 10188 KB Output is correct
5 Correct 7 ms 10188 KB Output is correct
6 Correct 6 ms 10188 KB Output is correct
7 Correct 6 ms 10188 KB Output is correct
8 Correct 6 ms 10196 KB Output is correct
9 Correct 6 ms 10188 KB Output is correct
10 Correct 5 ms 9932 KB Output is correct
11 Correct 7 ms 10204 KB Output is correct
12 Correct 6 ms 10200 KB Output is correct
13 Correct 17 ms 11044 KB Output is correct
14 Correct 15 ms 11048 KB Output is correct
15 Correct 10 ms 10988 KB Output is correct
16 Correct 11 ms 11084 KB Output is correct
17 Correct 14 ms 11084 KB Output is correct
18 Correct 10 ms 11084 KB Output is correct
19 Correct 13 ms 11128 KB Output is correct
20 Correct 10 ms 11124 KB Output is correct
21 Correct 8 ms 11048 KB Output is correct
22 Correct 13 ms 11144 KB Output is correct
23 Correct 13 ms 11084 KB Output is correct
24 Correct 15 ms 11040 KB Output is correct
25 Correct 438 ms 69072 KB Output is correct
26 Correct 415 ms 68924 KB Output is correct
27 Correct 495 ms 70552 KB Output is correct
28 Correct 392 ms 68360 KB Output is correct
29 Runtime error 101 ms 43052 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -