Submission #16924046


Source Code Expand

Copy
#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; using namespace atcoder;
void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan0
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int N, K, X[201010];
int Q;
//---------------------------------------------------------------------------------------------------
int toRight[201010], toLeft[201010];
int toR[19][201010], toL[19][201010];
int totR[19][201010], totL[19][201010];
//---------------------------------------------------------------------------------------------------
int getTot(int L, int R) {
	int res = 1;
	int cu = L;
	rrep(p, 18, 0) {
		if (toR[p][cu] <= R) {
			res += 1 << p;
			cu = toR[p][cu];
		}
	}
	return res;
}
int getRight(int L, int R) {
	int cnt = getTot(L, R);

	ll tot = R; cnt--;
	int cu = R;
	rep(p, 0, 19) if (cnt & (1 << p)) {
		tot += totL[p][cu];
		cu = toL[p][cu];
	}

	return tot;
}
int getLeft(int L, int R) {
	int cnt = getTot(L, R);

	ll tot = L; cnt--;
	int cu = L;
	rep(p, 0, 19) if (cnt & (1 << p)) {
		tot += totR[p][cu];
		cu = toR[p][cu];
	}

	return tot;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
	rep(i, 0, N) cin >> X[i];
	cin >> Q;

	rep(i, 0, N) toRight[i] = lower_bound(X, X + N, X[i] + K) - X;
	rep(i, 0, N) {
		int id = upper_bound(X, X + N, X[i] - K) - X;
		toLeft[i] = id - 1;
	}

	rep(p, 0, 19) toR[p][N] = N;
	rep(i, 0, N) toR[0][i] = toRight[i];
	rep(p, 1, 19) rep(i, 0, N) toR[p][i] = toR[p - 1][toR[p - 1][i]];

	rep(i, 0, N) totR[0][i] = toR[0][i];
	rep(p, 1, 19) rep(i, 0, N) totR[p][i] = totR[p - 1][i] + totR[p - 1][toR[p - 1][i]];

	rep(i, 0, N) toL[0][i] = toLeft[i];
	rep(p, 1, 19) rep(i, 0, N) {
		if (toL[p - 1][i] < 0) toL[p][i] = -1;
		else toL[p][i] = toL[p - 1][toL[p - 1][i]];
	}

	rep(i, 0, N) totL[0][i] = toL[0][i];
	rep(p, 1, 19) rep(i, 0, N) {
		if (toL[p - 1][i] < 0) totL[p][i] = totL[p - 1][i];
		else totL[p][i] = totL[p - 1][i] + totL[p - 1][toL[p - 1][i]];
	}

	rep(q, 0, Q) {
		int L, R; cin >> L >> R;
		L--; R--;
		ll ans = getRight(L, R) - getLeft(L, R) + getTot(L, R);
		printf("%lld\n", ans);
	}

}





Submission Info

Submission Time
Task D - Keep Distances
User hamayanhamayan
Language C++ (GCC 9.2.1 with AC Library)
Score 800
Code Size 3370 Byte
Status AC
Exec Time 690 ms
Memory 65808 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 2
AC × 23
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt
All 00-sample-01.txt, 00-sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 12 ms 3924 KB
00-sample-02.txt AC 4 ms 3920 KB
01-01.txt AC 3 ms 4056 KB
01-02.txt AC 690 ms 65748 KB
01-03.txt AC 679 ms 65648 KB
01-04.txt AC 644 ms 65808 KB
01-05.txt AC 663 ms 65624 KB
01-06.txt AC 648 ms 65724 KB
01-07.txt AC 650 ms 65756 KB
01-08.txt AC 562 ms 65640 KB
01-09.txt AC 447 ms 65780 KB
01-10.txt AC 337 ms 65720 KB
01-11.txt AC 251 ms 65696 KB
01-12.txt AC 173 ms 65648 KB
01-13.txt AC 682 ms 65756 KB
01-14.txt AC 662 ms 65644 KB
01-15.txt AC 538 ms 65648 KB
01-16.txt AC 466 ms 65684 KB
01-17.txt AC 400 ms 65700 KB
01-18.txt AC 294 ms 65804 KB
01-19.txt AC 263 ms 65700 KB
01-20.txt AC 205 ms 65668 KB
01-21.txt AC 176 ms 65624 KB