Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,abm,mmx,avx,avx2,popcnt")
- //#pragma GCC optimize("fast-math")
- #pragma GCC optimize("unroll-loops")
- //#pragma comment(linker, "/STACK:36777216")
- #define _CRT_SECURE_NO_WARNINGS
- #include <chrono>
- #include <set>
- #include <cstring>
- #include <map>
- #include <deque>
- #include <cmath>
- #include <queue>
- #include <cassert>
- #include <random>
- #include <bitset>
- #include <iomanip>
- #include <numeric>
- #include <time.h>//////////////
- #include <ctime>
- #include <string>
- #include <cstdio>
- #include <vector>
- #include <complex>
- #include <cstdlib>
- #include <iostream>
- #include <algorithm>
- #include <unordered_map>
- #include <unordered_set>
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- #define mp make_pair
- #define pbc push_back
- #define pob pop_back()
- #define empb emplace_back
- #define queuel queue<long long>
- #define sqr(a) ((a) * (a))
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- #define pin(p) cin >> p.first >> p.second;
- #define uniq(a) sort(all(a));(a).resize(unique(all(a)) - a.begin());
- #define rev(v) reverse(v.begin(), v.end());
- #define sout(s, c) for (auto i : s) cout << i << c;
- #define pout(p) cout << p.first << " " << p.second;
- #define er(v, l, r) erase(v.begin() + l, v.begin() + r);
- #define vin(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i];
- #define vout(v, c) for (int i = 0; i < v.size(); ++i) cout << v[i] << c;
- #define pushi(v, a) for (int i = 0; i < a.size(); ++i) v.push_back(a[i]);
- #define fastio() ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); srand(time(NULL))
- #define sp system("pause")
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- using namespace std;
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- typedef long long ll;
- typedef long double ld;
- typedef unsigned long long ull;
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- const ld EPS = 1e-8;
- const int inf = 1e9;
- const ld PI = acos(-1);
- int mod = (int)998244353;
- const int MOD7 = 1000000007;
- const int MOD9 = 1000000009;
- const int a228 = 18;
- const ll kekmod = 1791791791;
- const ll bestmod = 1148822869;
- const ll secmod = (int) 1e9 + 113;
- vector<ll> mods = { kekmod,bestmod,mod,MOD9,1000000007 };
- vector<ll> hashpows = { 29,31,37,43,47,53,179,229 };
- mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count() + 228 + 'i' + 'q' + 1337 + 1488);
- //ll MOD = mods[rnd() % mods.size()];
- //ll hashpow = hashpows[rand() % hashpows.size();
- const int MAXN = 5e4 + 1;
- int ans = 0;
- int k;
- set<int> keks;
- int a[MAXN];
- inline void add(int x)
- {
- auto jj = keks.upper_bound(x);
- if (jj == keks.begin() || jj == keks.end())
- {
- }
- else
- {
- auto lol = jj;
- ans -= ((*jj) - (*(--lol))) > k;
- }
- if (jj != keks.end()) ans += (*jj) - x > k;
- if (jj != keks.begin()) ans += (x - (*(--jj))) > k;
- keks.insert(x);
- }
- inline void del(int x)
- {
- auto kek = keks.upper_bound(x);
- auto lol = kek;
- int ta = (kek == keks.end() ? 0 : ((*kek) - x) > k);
- int tb = 0;
- kek--;
- if (kek != keks.begin())
- {
- kek--;
- tb = x - (*kek) > k;
- }
- ans -= ta + tb;
- if (lol == keks.end())
- {
- keks.erase(x);
- return;
- }
- if (lol == (++keks.begin()))
- {
- keks.erase(x);
- return;
- }
- ans += (*lol) - (*kek) > k;
- keks.erase(x);
- }
- int K;
- struct query
- {
- int l, r, i;
- };
- bool cmp(query a, query b)
- {
- if (a.l / K == b.l / K)
- {
- // return a.r < b.r;
- return (a.l / K % 2 ? a.r> b.r : a.r<b.r);
- }
- return a.l < b.l;
- }
- int anss[MAXN];
- query kekoses[MAXN];
- inline bool isdigit(char c)
- {
- return c >= '0' &&c <= '9';
- }
- #define _getchar_nolock getchar_unlocked
- inline int readInt()
- {
- int ans = 0;
- char c;
- while (c = _getchar_nolock())
- {
- if (isdigit(c))
- {
- ans = c - '0';
- break;
- }
- }
- while (c = _getchar_nolock())
- {
- if (!isdigit(c))break;
- ans *= 10;
- ans += c - '0';
- }
- return ans;
- }
- signed main()
- {
- fastio();
- int n, q;
- n = readInt();
- q = readInt();
- k = readInt();
- K = 200;
- //cin >> n >> q >> k;
- for (int i = 0; i < n; ++i)
- {
- //cin >> a[i];
- a[i] = readInt();
- }
- for (int i = 0; i < q; ++i)
- {
- kekoses[i].l = readInt();
- kekoses[i].r = readInt();
- // cin >> kekoses[i].l >> kekoses[i].r;
- kekoses[i].l--;
- kekoses[i].r--;
- kekoses[i].i = i;
- }
- sort(kekoses, kekoses + q, cmp);
- int l = 0, r = -1;
- for (int i = 0; i < q; ++i)
- {
- while (r < kekoses[i].r)
- {
- add(a[++r]);
- }
- while (r > kekoses[i].r)
- {
- del(a[r--]);
- }
- while (l > kekoses[i].l)
- {
- add(a[--l]);
- }
- while (l < kekoses[i].l)
- {
- del(a[l++]);
- }
- anss[kekoses[i].i] = ans;
- }
- for (int i = 0; i < q; ++i)
- {
- printf("%d ", anss[i] + 1);
- }
- sp;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement