제출 #1350751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1350751		guardianec	Bubble Sort Machine (JOI25_bubble)	C++20	5 / 100	2095 ms	19784 KiB

bubble

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n;
vector<ll> T;

void update(ll k, ll u) {
    k+=n;
    T[k] = u;
    for (k/=2; k>0; k/=2) {
        T[k] = T[2*k]+T[2*k+1];
    }
}

ll sum(ll a, ll b) {
    a+=n; b+=n;
    ll s = 0;
    while(a<=b) {
        if (a & 1) s+=T[a++];
        if (!(b & 1)) s+=T[b--];
        a/=2; b/=2;
    }
    return s;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    T.resize(2*n+1);
    vector<ll> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }

    for (int i=0; i<n; i++) {
        T[i+n] = a[i];
    }

    for (int i=n-1; i>0; i--) {
        T[i] = T[2*i]+T[2*i+1];
    }

    ll q;
    cin >> q;
    while(q--) {
        ll t;
        cin >> t;
        if (t==1) {
            for (int i=1; i<n; i++) {
                if (a[i]<a[i-1]) {
                    update(i, a[i-1]);
                    update(i-1, a[i]);
                    swap(a[i], a[i-1]);
                }
            }
        } else {
            ll l,r;
            cin >> l >> r;
            l--; r--;
            cout << sum(l,r) << "\n";
        }
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 29
• Subtask 6: 0 / 17