Submission #855919


Source Code Expand

Copy
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

#define N 100010
#define B 32

ll x[N], dp[B][N];
ll n, l, q;

int main(){
	cin>>n;
	rep(i, n) cin>>x[i];
	cin>>l>>q;
	x[n] = x[n-1]+l+1;
	{
		int lx = 0, rx = 0;
		while(lx < n){
			while(x[rx]-x[lx]<=l) rx++;
			dp[0][lx] = rx-1;
			lx++;
		}
		for(int i = 1; i < B; i++){
			for(int j = 0; j < n; j++){
				dp[i][j] = dp[i-1][dp[i-1][j]];
			}
		}
	}
	rep(_, q){
		int a, b;
		cin>>a>>b; a--; b--;
		if(a>b) swap(a, b);
		int lb = 0, ub = n-1; // (lb, ub]
		while(ub-lb>1){
			int md = (lb+ub+1)/2;
			int s = a;
			for(int j = 0; j < B; j++){
				if(1&(md>>j)) s = dp[j][s];
			}
			(b<=s?ub:lb)=md;
		}
		cout<<ub<<endl;
	}
	return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User Lepton
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1843 Byte
Status AC
Exec Time 1210 ms
Memory 26624 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 200 / 200 500 / 500
Status
AC × 1
AC × 14
AC × 27
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 384 KB
subtask1_01.txt AC 5 ms 384 KB
subtask1_02.txt AC 4 ms 384 KB
subtask1_03.txt AC 13 ms 640 KB
subtask1_04.txt AC 13 ms 640 KB
subtask1_05.txt AC 13 ms 640 KB
subtask1_06.txt AC 9 ms 512 KB
subtask1_07.txt AC 8 ms 512 KB
subtask1_08.txt AC 13 ms 640 KB
subtask1_09.txt AC 14 ms 640 KB
subtask1_10.txt AC 13 ms 640 KB
subtask1_11.txt AC 13 ms 640 KB
subtask1_12.txt AC 14 ms 640 KB
subtask1_13.txt AC 13 ms 640 KB
subtask2_01.txt AC 1115 ms 26496 KB
subtask2_02.txt AC 1193 ms 26624 KB
subtask2_03.txt AC 1115 ms 26368 KB
subtask2_04.txt AC 651 ms 17408 KB
subtask2_05.txt AC 715 ms 17536 KB
subtask2_06.txt AC 988 ms 26240 KB
subtask2_07.txt AC 1187 ms 26496 KB
subtask2_08.txt AC 1196 ms 26624 KB
subtask2_09.txt AC 1194 ms 26624 KB
subtask2_10.txt AC 1210 ms 26624 KB
subtask2_11.txt AC 1210 ms 24704 KB
subtask2_12.txt AC 974 ms 26624 KB
subtask2_13.txt AC 976 ms 26240 KB