提出 #856770


ソースコード 拡げる

Copy
#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<pair<int, int>> qs(q);
    for (auto &q: qs) scanf("%d%d", &q.first, &q.second), q.first--, q.second--;

    // 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) {
        int ans = 0, cur = q.first, goal = q.second;
        if (cur > goal) swap(cur, goal);

        while (cur < goal) {
            // cerr << "* " << cur << endl;
            int longest = 0, next = cur;
            for (int i = 0; i < logs; i++) {
                if (skip[i][cur] > goal) break;
                else {
                    longest = 1 << i;
                    next = skip[i][cur];
                }
            }
            cur = next;
            ans += longest;
        }

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

    return 0;
}

提出情報

提出日時
問題 E - 高橋君とホテル
ユーザ tanakh
言語 C++14 (GCC 5.4.1)
得点 0
コード長 1777 Byte
結果 TLE
実行時間 3157 ms
メモリ 8576 KB

コンパイルエラー

./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:27:80: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for (auto &q: qs) scanf("%d%d", &q.first, &q.second), q.first--, q.second--;
                                                                                ^

ジャッジ結果

セット名 Sample Subtask1 All
得点 / 配点 0 / 0 0 / 200 0 / 500
結果
AC × 1
AC × 4
TLE × 10
AC × 5
TLE × 22
セット名 テストケース
Sample example_01.txt
Subtask1 example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt
All example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt
ケース名 結果 実行時間 メモリ
example_01.txt AC 4 ms 256 KB
subtask1_01.txt TLE 3153 ms 256 KB
subtask1_02.txt AC 6 ms 256 KB
subtask1_03.txt TLE 3153 ms 384 KB
subtask1_04.txt AC 5 ms 384 KB
subtask1_05.txt TLE 3157 ms 384 KB
subtask1_06.txt AC 5 ms 384 KB
subtask1_07.txt TLE 3153 ms 384 KB
subtask1_08.txt TLE 3157 ms 384 KB
subtask1_09.txt TLE 3153 ms 384 KB
subtask1_10.txt TLE 3153 ms 384 KB
subtask1_11.txt TLE 3153 ms 384 KB
subtask1_12.txt TLE 3153 ms 384 KB
subtask1_13.txt TLE 3153 ms 384 KB
subtask2_01.txt TLE 3154 ms 8064 KB
subtask2_02.txt AC 167 ms 8576 KB
subtask2_03.txt TLE 3154 ms 8064 KB
subtask2_04.txt TLE 3154 ms 5376 KB
subtask2_05.txt TLE 3157 ms 5376 KB
subtask2_06.txt TLE 3154 ms 8064 KB
subtask2_07.txt TLE 3154 ms 8064 KB
subtask2_08.txt TLE 3154 ms 8064 KB
subtask2_09.txt TLE 3154 ms 8064 KB
subtask2_10.txt TLE 3154 ms 8064 KB
subtask2_11.txt TLE 3154 ms 7552 KB
subtask2_12.txt TLE 3154 ms 8064 KB
subtask2_13.txt TLE 3154 ms 8064 KB