oj.uz

Submission #634662

# Submission time Handle Problem Language Result Execution time Memory
634662 2022-08-24T16:35:35 Z someone Railway Trip 2 (JOI22_ho_t4) C++14
100 / 100
 434 ms 156452 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Node {
    int deb, fin, mini, maxi;
};

const int T = 17, M = 1 << T, N = 2 * M;

int n, m, k, q;
Node node[T][N];
vector<int> deb[M], fin[M];

pair<int, int> getInter(int iTree, int d, int f) {
    //cout << d << ' ' << f << '\n';
    int l = d, r = f;

    d += M-1, f += M;
    while(d + 1 < f) {
        if(f & 1) {
            l = min(l, node[iTree][f - 1].mini);
            r = max(r, node[iTree][f - 1].maxi);
            //cout << ' ' << f-1 << ' ' << node[iTree][f - 1].mini << ' ' << node[iTree][f - 1].maxi << '\n';
        }
        if(!(d & 1)) {
            l = min(l, node[iTree][d + 1].mini);
            r = max(r, node[iTree][d + 1].maxi);
            //cout << ' ' << d+1 << ' ' << node[iTree][d + 1].mini << ' ' << node[iTree][d + 1].maxi << '\n';
        }
        d >>= 1;
        f >>= 1;
    }

    return {l, r};
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout.tie(0);

    cin >> n >> k >> m;
    for(int i = 0; i < M; i++)
        node[0][i + M].deb = i,
        node[0][i + M].fin = i+1;
    for(int i = M-1; i > 0; i--)
        node[0][i].deb = node[0][i*2].deb,
        node[0][i].fin = node[0][i*2+1].fin;
    for(int i = 1; i < N; i++)
        node[0][i].mini = node[0][i].deb,
        node[0][i].maxi = node[0][i].fin;
    for(int i = 1; i < T; i++)
        for(int j = 1; j < N; j++)
            node[i][j].deb = node[i-1][j].deb,
            node[i][j].fin = node[i-1][j].fin,
            node[i][j].mini = node[i-1][j].mini,
            node[i][j].maxi = node[i-1][j].maxi;

    for(int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        if(a < b) {
            fin[a].push_back(b+1);
            if(a + k <= n)
                fin[a + k].push_back(-b-1);
        } else {
            deb[a].push_back(b);
            if(a - k > 0)
                deb[a - k].push_back(-b);
        }
    }
    deque<int> mini, maxi;
    for(int i = 1; i <= n; i++) {
        for(int upd : fin[i]) {
            if(upd < 0) {
                if(!maxi.empty() && maxi[0] == -upd)
                    maxi.pop_front();
            } else {
                while(!maxi.empty() && maxi.back() < upd)
                    maxi.pop_back();
                maxi.push_back(upd);
            }
        }
        if(!maxi.empty())
            node[0][i + M].maxi = max(node[0][i + M].maxi, maxi[0]);
    }
    for(int i = n; i > 0; i--) {
        for(int upd : deb[i]) {
            if(upd < 0) {
                if(!mini.empty() && mini[0] == -upd)
                    mini.pop_front();
            } else {
                while(!mini.empty() && mini.back() > upd)
                    mini.pop_back();
                mini.push_back(upd);
            }
        }
        if(!mini.empty())
            node[0][i + M].mini = min(node[0][i + M].mini, mini[0]);
    }
    for(int i = M-1; i > 0; i--)
        node[0][i].mini = min(node[0][i*2].mini, node[0][i*2+1].mini),
        node[0][i].maxi = max(node[0][i*2].maxi, node[0][i*2+1].maxi);

    for(int i = 1; i < T; i++) {
        for(int j = 1; j <= n; j++) {
            pair<int, int> inter = getInter(i-1, node[i-1][j + M].mini, node[i-1][j + M].maxi);
            node[i][j + M].mini = inter.first,
            node[i][j + M].maxi = inter.second;
            //cout << j << ' ' << inter.first << ' ' << inter.second << '\n';
        }
        for(int j = M-1; j > 0; j--)
            node[i][j].mini = min(node[i][j*2].mini, node[i][j*2+1].mini),
            node[i][j].maxi = max(node[i][j*2].maxi, node[i][j*2+1].maxi);
    }

    cin >> q;
    for(int i = 0; i < q; i++) {
        int s, t; cin >> s >> t;

        int l = s, r = s + 1, nb = 0;
        for(int j = T-1; j > -1; j--) {
            pair<int, int> inter = getInter(j, l, r);
            if(t < inter.first || inter.second <= t) {
                nb += (1 << j);
                l = inter.first, r = inter.second;
            }
        }
        if(nb + 1 == (1 << T))
            cout << "-1\n";
        else
            cout << nb+1 << '\n';
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 146044 KB Output is correct
2 Correct 77 ms 146004 KB Output is correct
3 Correct 74 ms 145952 KB Output is correct
4 Correct 74 ms 145964 KB Output is correct
5 Correct 87 ms 145940 KB Output is correct
6 Correct 85 ms 145884 KB Output is correct
7 Correct 92 ms 145956 KB Output is correct
8 Correct 77 ms 146008 KB Output is correct
9 Correct 83 ms 145928 KB Output is correct
10 Correct 77 ms 145892 KB Output is correct
11 Correct 83 ms 146060 KB Output is correct
12 Correct 100 ms 145984 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 146044 KB Output is correct
2 Correct 77 ms 146004 KB Output is correct
3 Correct 74 ms 145952 KB Output is correct
4 Correct 74 ms 145964 KB Output is correct
5 Correct 87 ms 145940 KB Output is correct
6 Correct 85 ms 145884 KB Output is correct
7 Correct 92 ms 145956 KB Output is correct
8 Correct 77 ms 146008 KB Output is correct
9 Correct 83 ms 145928 KB Output is correct
10 Correct 77 ms 145892 KB Output is correct
11 Correct 83 ms 146060 KB Output is correct
12 Correct 100 ms 145984 KB Output is correct
13 Correct 87 ms 146036 KB Output is correct
14 Correct 79 ms 145996 KB Output is correct
15 Correct 77 ms 145968 KB Output is correct
16 Correct 81 ms 146012 KB Output is correct
17 Correct 81 ms 146056 KB Output is correct
18 Correct 80 ms 146028 KB Output is correct
19 Correct 98 ms 146060 KB Output is correct
20 Correct 79 ms 146060 KB Output is correct
21 Correct 80 ms 146004 KB Output is correct
22 Correct 84 ms 146076 KB Output is correct
23 Correct 86 ms 146000 KB Output is correct
24 Correct 81 ms 146056 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 149880 KB Output is correct
2 Correct 190 ms 149708 KB Output is correct
3 Correct 226 ms 150204 KB Output is correct
4 Correct 175 ms 149704 KB Output is correct
5 Correct 206 ms 153644 KB Output is correct
6 Correct 234 ms 154444 KB Output is correct
7 Correct 201 ms 155940 KB Output is correct
8 Correct 188 ms 150996 KB Output is correct
9 Correct 178 ms 149440 KB Output is correct
10 Correct 228 ms 155332 KB Output is correct
11 Correct 198 ms 152572 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 150320 KB Output is correct
2 Correct 297 ms 152928 KB Output is correct
3 Correct 302 ms 151120 KB Output is correct
4 Correct 244 ms 156452 KB Output is correct
5 Correct 221 ms 152752 KB Output is correct
6 Correct 223 ms 152824 KB Output is correct
7 Correct 283 ms 153232 KB Output is correct
8 Correct 343 ms 153160 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 154840 KB Output is correct
2 Correct 337 ms 151084 KB Output is correct
3 Correct 311 ms 149060 KB Output is correct
4 Correct 289 ms 147532 KB Output is correct
5 Correct 227 ms 147200 KB Output is correct
6 Correct 237 ms 146680 KB Output is correct
7 Correct 223 ms 151804 KB Output is correct
8 Correct 87 ms 145952 KB Output is correct
9 Correct 80 ms 146172 KB Output is correct
10 Correct 234 ms 154208 KB Output is correct
11 Correct 256 ms 152176 KB Output is correct
12 Correct 253 ms 154956 KB Output is correct
13 Correct 264 ms 153996 KB Output is correct
14 Correct 80 ms 145888 KB Output is correct
15 Correct 80 ms 146164 KB Output is correct
16 Correct 253 ms 154572 KB Output is correct
17 Correct 360 ms 152540 KB Output is correct
18 Correct 352 ms 155204 KB Output is correct
19 Correct 344 ms 155276 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 146044 KB Output is correct
2 Correct 77 ms 146004 KB Output is correct
3 Correct 74 ms 145952 KB Output is correct
4 Correct 74 ms 145964 KB Output is correct
5 Correct 87 ms 145940 KB Output is correct
6 Correct 85 ms 145884 KB Output is correct
7 Correct 92 ms 145956 KB Output is correct
8 Correct 77 ms 146008 KB Output is correct
9 Correct 83 ms 145928 KB Output is correct
10 Correct 77 ms 145892 KB Output is correct
11 Correct 83 ms 146060 KB Output is correct
12 Correct 100 ms 145984 KB Output is correct
13 Correct 87 ms 146036 KB Output is correct
14 Correct 79 ms 145996 KB Output is correct
15 Correct 77 ms 145968 KB Output is correct
16 Correct 81 ms 146012 KB Output is correct
17 Correct 81 ms 146056 KB Output is correct
18 Correct 80 ms 146028 KB Output is correct
19 Correct 98 ms 146060 KB Output is correct
20 Correct 79 ms 146060 KB Output is correct
21 Correct 80 ms 146004 KB Output is correct
22 Correct 84 ms 146076 KB Output is correct
23 Correct 86 ms 146000 KB Output is correct
24 Correct 81 ms 146056 KB Output is correct
25 Correct 187 ms 149880 KB Output is correct
26 Correct 190 ms 149708 KB Output is correct
27 Correct 226 ms 150204 KB Output is correct
28 Correct 175 ms 149704 KB Output is correct
29 Correct 206 ms 153644 KB Output is correct
30 Correct 234 ms 154444 KB Output is correct
31 Correct 201 ms 155940 KB Output is correct
32 Correct 188 ms 150996 KB Output is correct
33 Correct 178 ms 149440 KB Output is correct
34 Correct 228 ms 155332 KB Output is correct
35 Correct 198 ms 152572 KB Output is correct
36 Correct 295 ms 150320 KB Output is correct
37 Correct 297 ms 152928 KB Output is correct
38 Correct 302 ms 151120 KB Output is correct
39 Correct 244 ms 156452 KB Output is correct
40 Correct 221 ms 152752 KB Output is correct
41 Correct 223 ms 152824 KB Output is correct
42 Correct 283 ms 153232 KB Output is correct
43 Correct 343 ms 153160 KB Output is correct
44 Correct 385 ms 154840 KB Output is correct
45 Correct 337 ms 151084 KB Output is correct
46 Correct 311 ms 149060 KB Output is correct
47 Correct 289 ms 147532 KB Output is correct
48 Correct 227 ms 147200 KB Output is correct
49 Correct 237 ms 146680 KB Output is correct
50 Correct 223 ms 151804 KB Output is correct
51 Correct 87 ms 145952 KB Output is correct
52 Correct 80 ms 146172 KB Output is correct
53 Correct 234 ms 154208 KB Output is correct
54 Correct 256 ms 152176 KB Output is correct
55 Correct 253 ms 154956 KB Output is correct
56 Correct 264 ms 153996 KB Output is correct
57 Correct 80 ms 145888 KB Output is correct
58 Correct 80 ms 146164 KB Output is correct
59 Correct 253 ms 154572 KB Output is correct
60 Correct 360 ms 152540 KB Output is correct
61 Correct 352 ms 155204 KB Output is correct
62 Correct 344 ms 155276 KB Output is correct
63 Correct 334 ms 150460 KB Output is correct
64 Correct 359 ms 150900 KB Output is correct
65 Correct 338 ms 150508 KB Output is correct
66 Correct 434 ms 153360 KB Output is correct
67 Correct 366 ms 155344 KB Output is correct
68 Correct 254 ms 155592 KB Output is correct
69 Correct 238 ms 154856 KB Output is correct
70 Correct 332 ms 156068 KB Output is correct
71 Correct 345 ms 156076 KB Output is correct