Submission #856342


Source Code Expand

Copy
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <list>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <iterator> 
#include <limits>

#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(A) (a).rbegin(),(a).rend()
#define PB push_back
#define MP make_pair

#define dump(x) cerr << #x << " = " << (x) << endl;

using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

int N, L, Q;
VI X;

int calc(int a, int b) {
    int now = a;
    int res = 0;
    while (true) {
        if (now >= b) {
            break;
        }
        now = distance(X.begin(), upper_bound(ALL(X), X[now] + L)) - 1;
        //cout << now << endl;
        res += 1;
    }
    return res;
}

int main(int argc, char const* argv[])
{
    cin >> N;
    REP(i, N) {
        int x; cin >> x;
        X.PB(x);
    }
    cin >> L;
    cin >> Q;
    REP(q, Q) {
        int a, b;
        cin >> a >> b;
        if (a > b) {
            swap(a, b);
        }
        a -= 1; b -= 1;
        cout << calc(a, b) << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User poyodr
Language C++14 (GCC 5.4.1)
Score 200
Code Size 1616 Byte
Status TLE
Exec Time 3153 ms
Memory 892 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 0 / 500
Status
AC × 1
AC × 14
AC × 17
TLE × 10
Set Name Test Cases
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
Case Name Status Exec Time Memory
example_01.txt AC 4 ms 256 KB
subtask1_01.txt AC 4 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt AC 13 ms 256 KB
subtask1_04.txt AC 35 ms 256 KB
subtask1_05.txt AC 12 ms 256 KB
subtask1_06.txt AC 11 ms 256 KB
subtask1_07.txt AC 8 ms 256 KB
subtask1_08.txt AC 11 ms 256 KB
subtask1_09.txt AC 13 ms 256 KB
subtask1_10.txt AC 23 ms 256 KB
subtask1_11.txt AC 24 ms 256 KB
subtask1_12.txt AC 23 ms 256 KB
subtask1_13.txt AC 20 ms 256 KB
subtask2_01.txt TLE 3153 ms 892 KB
subtask2_02.txt TLE 3153 ms 892 KB
subtask2_03.txt TLE 3153 ms 892 KB
subtask2_04.txt AC 526 ms 764 KB
subtask2_05.txt TLE 3153 ms 640 KB
subtask2_06.txt AC 793 ms 892 KB
subtask2_07.txt TLE 3153 ms 892 KB
subtask2_08.txt TLE 3153 ms 892 KB
subtask2_09.txt TLE 3153 ms 892 KB
subtask2_10.txt TLE 3153 ms 892 KB
subtask2_11.txt TLE 3153 ms 892 KB
subtask2_12.txt TLE 3153 ms 892 KB
subtask2_13.txt AC 777 ms 892 KB