Submission #49997043

Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll=long long;
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(p) p.begin(), p.end()

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<int> A(N), P(N), inv(N), SA(N);
    rep(i, 0, N) cin >> A[i], inv[i] = i;
    sort(all(inv), [&](int l, int r){
        return A[l] < A[r];
    });
    rep(i, 0, N) SA[i] = A[inv[i]], P[inv[i]] = i;
    const int B = 64;
    int len = (N + B - 1)/B;
    vector S(len + 1, (vector<ll> (len + 1)));
    rep(i, 0, N){
        S[i / B + 1][P[i] / B + 1] += A[i];
    }
    rep(i, 0, len) rep(j, 0, len + 1) S[i + 1][j] += S[i][j];
    rep(i, 0, len + 1) rep(j, 0, len) S[i][j + 1] += S[i][j];

    auto f = [&](int r, int a) -> ll {
        ll res = S[r / B][a / B];
        int br = B * (r / B), ba = B * (a / B);
        rep(i, br, r) res += A[i] * (P[i] < a);
        rep(j, ba, a) res += A[inv[j]] * (inv[j] < br);
        return res;
    };

    ll ans = 0;
    int Q;
    cin >> Q;
    rep(i, 0, Q){
        ll L, R, X;
        cin >> L >> R >> X;
        L ^= ans;
        R ^= ans;
        X ^= ans;
        int Y = upper_bound(all(SA), int(X)) - SA.begin();
        ans = f(R, Y) - f(L - 1, Y);
        cout << ans << "\n";
    }
}

Submission Info

Submission Time
Task G - Smaller Sum
User potato167
Language C++ 17 (gcc 12.2)
Score 600
Code Size 1395 Byte
Status AC
Exec Time 231 ms
Memory 83108 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 1
AC × 51
Set Name Test Cases
Sample sample_01.txt
All sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 3520 KiB
test_01.txt AC 9 ms 4568 KiB
test_02.txt AC 8 ms 5944 KiB
test_03.txt AC 79 ms 23640 KiB
test_04.txt AC 61 ms 49528 KiB
test_05.txt AC 18 ms 3528 KiB
test_06.txt AC 110 ms 24444 KiB
test_07.txt AC 175 ms 50248 KiB
test_08.txt AC 192 ms 59020 KiB
test_09.txt AC 55 ms 3552 KiB
test_10.txt AC 43 ms 30200 KiB
test_11.txt AC 60 ms 5924 KiB
test_12.txt AC 76 ms 64828 KiB
test_13.txt AC 44 ms 38380 KiB
test_14.txt AC 69 ms 8308 KiB
test_15.txt AC 57 ms 9840 KiB
test_16.txt AC 129 ms 25224 KiB
test_17.txt AC 69 ms 30168 KiB
test_18.txt AC 27 ms 3716 KiB
test_19.txt AC 85 ms 13844 KiB
test_20.txt AC 63 ms 3600 KiB
test_21.txt AC 122 ms 82728 KiB
test_22.txt AC 135 ms 82640 KiB
test_23.txt AC 143 ms 82864 KiB
test_24.txt AC 204 ms 82712 KiB
test_25.txt AC 216 ms 82712 KiB
test_26.txt AC 221 ms 82704 KiB
test_27.txt AC 223 ms 82972 KiB
test_28.txt AC 225 ms 82968 KiB
test_29.txt AC 228 ms 83068 KiB
test_30.txt AC 113 ms 82724 KiB
test_31.txt AC 129 ms 82716 KiB
test_32.txt AC 139 ms 82640 KiB
test_33.txt AC 143 ms 82764 KiB
test_34.txt AC 207 ms 82804 KiB
test_35.txt AC 218 ms 82712 KiB
test_36.txt AC 221 ms 82800 KiB
test_37.txt AC 227 ms 82972 KiB
test_38.txt AC 228 ms 82984 KiB
test_39.txt AC 231 ms 83012 KiB
test_40.txt AC 112 ms 82728 KiB
test_41.txt AC 113 ms 82732 KiB
test_42.txt AC 120 ms 82868 KiB
test_43.txt AC 128 ms 82752 KiB
test_44.txt AC 175 ms 82740 KiB
test_45.txt AC 191 ms 82768 KiB
test_46.txt AC 194 ms 82744 KiB
test_47.txt AC 200 ms 83108 KiB
test_48.txt AC 199 ms 83092 KiB
test_49.txt AC 202 ms 83104 KiB
test_50.txt AC 104 ms 82716 KiB