Submission #856855

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
using namespace std;

const int logs = 17;
int skip[17][100000];

int main()
{
    int n;
    scanf("%d", &n);

    vector<int> xs(n);
    for (auto &x: xs) scanf("%d", &x);

    int l, q;
    scanf("%d%d", &l, &q);

    // vector<vector<int>> skip(17, vector<int>(n));

    for (int j = 0; j < n; j++) {
        if (j == n - 1) skip[0][j] = n;
        else skip[0][j] = prev(upper_bound(xs.begin(), xs.end(), xs[j] + l)) - xs.begin();
    }

    for (int i = 1; i < logs; i++) {
        for (int j = 0; j < n; j++) {
            skip[i][j] = skip[i - 1][j];
            if (skip[i][j] < n) skip[i][j] = skip[i - 1][skip[i][j]];
        }

    }

    // for (int i = 0; i < skip.size(); i++) {
    //     for (int j = 0; j < n; j++) {
    //         cerr << i << ", " << j << ": " << skip[i][j] << endl;
    //     }
    //     cerr << endl;
    // }

    //for (auto &q: qs) {
    while (q--) {
        // vector<pair<int, int>> qs(q);
        // for (auto &q: qs) scanf("%d%d", &q.first, &q.second), q.first--, q.second--;
        int ans = 0, cur, goal;
        scanf("%d%d", &cur, &goal);
        cur--, goal--;

        if (cur > goal) swap(cur, goal);

        int span = logs - 1;

        while (cur < goal) {
            // cerr << "* " << cur << endl;
            // int longest = 0, next = cur;

            while (span > 0 && skip[span][cur] > goal) span--;
            cur = skip[span][cur];
            ans += 1 << span;
        }

        printf("%d\n", ans);
    }

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:18:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:21:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for (auto &x: xs) scanf("%d", &x);
                                      ^
./Main.cpp:24:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &l, &q);
                          ^
./Main.cpp:53:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &cur, &goal);
                                   ^

Judge Result