提出 #42149608

---

ソースコード 拡げる

#include <atcoder/all>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;
#define REP(i, m, n) for (int i = (int) (m); i < (int) (n); ++i)
#define rep(i, n) REP(i, 0, n)
using ll = long long;
#define pint pair<int, int>
#define pll pair<ll, ll>
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;

using mint = modint998244353;


int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
//    rep(i, n)a[i] = 0;
    rep(i, n) {
        cin >> a[i];
    }
    vector<ll> sum(n + 1);
    rep(i, n) {
        if (i % 2 == 1) {
            sum[i + 1] = sum[i] + (a[i + 1] - a[i]);
        } else {
            sum[i + 1] = sum[i];
        }
    }
//    rep(i, n + 1)cout << sum[i] << endl;
    ll q;
    cin >> q;
    rep(i, q) {
        ll l, r;
        cin >> l >> r;
        ll below = std::lower_bound(a.begin(), a.end(), l) - a.begin();
        ll above = std::upper_bound(a.begin(), a.end(), r) - a.begin();
        if (above == n)above--;
        while (a[above] > r) {
            above--;
        }
        ll ans = sum[above] - sum[below];
//        cout << below << ' ' << above << endl;
//        cout << l << ' ' << r << endl;
        if (below % 2 == 0) {
            ans += (a[below] - l);
        }
        if(above % 2 == 1){
            ans += (r - a[above]);
        }
        cout << ans << endl;
    }


    return 0;
}

提出情報

ジャッジ結果