Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Слава Україні, Героям слава
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 2e5 + 7, LOG = 18;
- const int NN = N * LOG;
- namespace pseg {
- pair<int, long long> seg[NN];
- int roots[N], cnt = 1;
- int L[NN], R[NN];
- void build(int p = 1, int l = 1, int r = (1 << LOG)) {
- if(l == r) {
- seg[p] = {0, 0};
- return;
- }
- int mid = (l + r) >> 1;
- L[p] = cnt++;
- R[p] = cnt++;
- build(L[p], l, mid);
- build(R[p], mid + 1, r);
- }
- void insert(int x, int val, int pcur = -1, int p = -1, int l = 1, int r = (1 << LOG)) {
- if(pcur == -1) {
- pcur = roots[x] = cnt++;
- }
- if(p == -1) {
- p = roots[x - 1];
- }
- seg[pcur] = seg[p];
- seg[pcur].first++;
- seg[pcur].second += val;
- if(l == r) {
- return;
- }
- int mid = (l + r) >> 1;
- if(val > mid) {
- L[pcur] = L[p];
- R[pcur] = cnt++;
- seg[R[pcur]] = seg[R[p]];
- insert(x, val, R[pcur], R[p], mid + 1, r);
- } else {
- R[pcur] = R[p];
- L[pcur] = cnt++;
- seg[L[pcur]] = seg[L[p]];
- insert(x, val, L[pcur], L[p], l, mid);
- }
- }
- pair<int, long long> find(int p, int i, int j, int l = 1, int r = (1 << LOG)) {
- if(i > r or j < l) {
- return {0, 0};
- }
- if(i <= l and r <= j) {
- return seg[p];
- }
- int mid = (l + r) >> 1;
- auto a = find(L[p], i, j, l, mid);
- auto b = find(R[p], i, j, mid + 1, r);
- return {a.first + b.first, a.second + b.second};
- }
- };
- int query(int l, int r, int a, int b, long long s) {
- int ans = 0, al = a, ar = b, lef = a, mn = -1;
- long long dd = 0;
- while(al <= ar) {
- int mid = (al + ar) >> 1;
- auto ll = pseg::find(pseg::roots[l - 1], mid, b);
- auto rr = pseg::find(pseg::roots[r], mid, b);
- if(s * (rr.first - ll.first) <= rr.second - ll.second) {
- ans = rr.first - ll.first;
- dd = rr.second - ll.second;
- lef = mid;
- ar = mid - 1;
- } else {
- mn = mid;
- al = mid + 1;
- }
- }
- if(lef == a) {
- return ans;
- }
- auto ll = pseg::find(pseg::roots[l - 1], mn, b);
- auto rr = pseg::find(pseg::roots[r], mn, b);
- if(rr.first - ll.first == ans) {
- return ans;
- }
- int add = (ans * s - dd) / (mn - s);
- add = abs(add);
- return ans + add;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int n;
- cin >> n;
- pseg::build();
- for(int i = 1; i <= n; i++) {
- int x;
- cin >> x;
- pseg::insert(i, x);
- }
- int q;
- cin >> q;
- while(q--) {
- int l, r, a, b, s;
- cin >> l >> r >> a >> b >> s;
- cout << query(l, r, a, b, s) << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement