제출 #1190714

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190714		lopkus	Fish 3 (JOI24_fish3)	C++20	0 / 100	161 ms	12704 KiB

Main

#include <bits/stdc++.h>

const int N = 3e5 + 5;

struct segtree{
    int64_t t[4*N] = {0};
    int64_t query(int v, int tl, int tr, int l, int r) {
        if(tl > r || tr < l) {
            return 0;
        }
        if(tl >= l && tr <= r) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        return (query(v * 2, tl, tm, l, r) + query(v * 2 + 1, tm + 1, tr, l, r));
    }
    void update(int v, int tl, int tr, int index, int64_t value) {
        if(tl == tr) {
            t[v] = value;
        }
        else {
            int tm = (tl + tr) / 2;
            if(index <= tm) {
                update(v * 2, tl, tm, index, value);
            }
            else {
                update(v * 2 + 1, tm + 1, tr, index, value);
            }
            t[v] = (t[v * 2] + t[v * 2 + 1]);
        }
    }
}seg;

void solve() {
  int n, d;
  std::cin >> n >> d;
  std::vector<int64_t> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  assert(d == 1);
  for(int i = 2; i <= n; i++) {
    if(a[i] < a[i - 1]) {
      seg.update(1, 1, n, i, a[i - 1] - a[i]);
    }
  }
  int q;
  std::cin >> q;
  while(q--) {
    int l, r;
    std::cin >> l >> r;
    std::cout << seg.query(1, 1, n, l + 1, r) << "\n";
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 7
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36