Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ∧_∧
- ( ・ω・。)つ━☆・*。
- ⊂ ノ ・゜
- しーJ Accepted
- */
- // #pragma GCC optimize("O3")
- // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define ll long long
- #define all(x) begin(x), end(x)
- #define x first
- #define y second
- #define int long long
- using namespace std;
- using namespace __gnu_pbds;
- typedef long double ld;
- template<typename T>
- using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- const ld PI = atan2(0, -1);
- void seriy() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout << fixed << setprecision(14);
- #ifdef _offline
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
- const int MAXN = 1e6;
- const int MAXM = 600;
- const int INF = 1e18 + 7;
- const int BASE = 47;
- const int MOD = 1e9 + 7;
- const int MAXLOG = 51;
- const ld EPS = 1e-6;
- struct node {
- int mx, pos;
- };
- struct rq {
- int l, r, num;
- };
- vector<node> t(4 * MAXN, {-INF, INF});
- int cur = 1;
- int n, q, k;
- node get(int v, int tl, int tr, int l, int r) {
- if(tl > r || tr < l) {
- return {-INF, INF};
- }
- if(tl >= l && tr <= r) {
- return t[v];
- }
- int tm = (tl + tr) >> 1;
- node left = get(v * 2 + 1, tl, tm, l, r);
- node right = get(v * 2 + 2, tm + 1, tr, l, r);
- if(left.mx > right.mx) {
- return left;
- }
- else {
- return right;
- }
- }
- void update(int v, int tl, int tr, int pos, int val) {
- if(tl > pos || tr < pos) {
- return;
- }
- if(tl == tr) {
- t[v] = {val, n - val};
- return;
- }
- int tm = (tl + tr) >> 1;
- update(v * 2 + 1, tl, tm, pos, val);
- update(v * 2 + 2, tm + 1, tr, pos, val);
- if(t[v * 2 + 1].mx > t[v * 2 + 2].mx) {
- t[v] = t[v * 2 + 1];
- }
- else {
- t[v] = t[v * 2 + 2];
- }
- }
- signed main() {
- seriy();
- cin >> n >> q >> k;
- vector<int> a(n);
- vector<pair<int, int>> lol(n);
- for(int i = 0; i < n; i++) {
- cin >> a[i];
- lol[i] = {a[i], a[i]};
- }
- vector<int> b = a;
- b.push_back(INF);
- b.push_back(-INF);
- sort(all(b));
- vector<rq> req(q);
- vector<vector<pair<int, int>>> rr(n);
- for(int j = 0; j < q; j++) {
- int l, r;
- cin >> l >> r;
- l--;
- r--;
- rr[l].push_back({r, j});
- req[j] = {l, r, j};
- }
- vector<int> res(q);
- vector<pair<int, int>> close(n, {-INF, INF});
- for(int i = n - 1; i >= 0; i--) {
- int pos = lower_bound(all(b), a[i]) - b.begin();
- int pos3 = upper_bound(all(b), lol[i].y + k) - b.begin() - 1;
- close[i].y = get(0, 0, b.size() - 1, pos, pos3).pos;
- // cerr << close[i].y << " ";
- // for(auto j : rr[i]) {
- // int ans = 0;
- // for(int p = i; p <= j.x; p++) {
- // if(close[p].x <= j.x && (close[close[p].x].x > j.x)) ans++;
- // if(close[p].y <= j.x && (close[close[p].y].y > j.x)) ans++;
- // }
- // res[j.y] = ans;
- // }
- update(0, 0, b.size() - 1, pos, cur);
- cur++;
- }
- cur = 0;
- fill(all(t), node{-INF, INF});
- for(int i = 0; i < n; i++) {
- int pos = lower_bound(all(b), a[i]) - b.begin();
- int pos3 = upper_bound(all(b), lol[i].y + k) - b.begin() - 1;
- close[i].x = get(0, 0, b.size() - 1, pos, pos3).mx;
- if(close[i].x == INF) close[i].x = -INF;
- // cerr << close[i].y << " ";
- // for(auto j : rr[i]) {
- // int ans = 0;
- // for(int p = i; p <= j.x; p++) {
- // if(close[p].x <= j.x && (close[close[p].x].x > j.x)) ans++;
- // if(close[p].y <= j.x && (close[close[p].y].y > j.x)) ans++;
- // }
- // res[j.y] = ans;
- // }
- update(0, 0, b.size() - 1, pos, cur);
- cur++;
- }
- for(int i = 0; i < q; i++) {
- // cerr << res[i] << " ";
- for(int j = req[i].l; j <= req[i].r; j++) {
- if(close[j].x < req[i].l && close[j].y > req[i].r) res[i]++;
- }
- cout << res[i] << " ";
- // cout << req[i].r - req[i].l + 1 - res[i] << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement