제출 #1243816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243816		mihajlo18	Addk (eJOI21_addk)	C++17	100 / 100	249 ms	8888 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll zbir(int l, int r, vector<ll> & drvo, int & tl, int & tr, int u){
    if(tr < l or tl > r){
        ll nula = 0;
        return nula;
    }
    else if(l <= tl and tr <= r){
        return drvo[u];
    }
    int tm = (tl + tr) / 2;
    int tm1 = tm + 1;
    return zbir(l, min(tm, r), drvo, tl, tm, 2 * u) + zbir(max(l, tm1), r, drvo, tm1, tr, 2 * u + 1);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<ll>brojevi(n);
    for(int i = 0; i < n; i++){
        cin >> brojevi[i];
    }
    int dva = 1;
    while(dva < n){
        dva *= 2;
    }
    int m = 2 * dva;
    vector<ll>drvo(m, 0);
    vector<ll>drvogore(m, 0);
    vector<ll>drvodole(m, 0);
    for(int i = dva; i < dva + n; i++){
        drvo[i] = brojevi[i - dva];
        drvogore[i] = brojevi[i - dva] * (i - dva + 1);
        drvodole[i] = brojevi[i - dva] * (n - (i - dva));
    }
    for(int i = (dva - 1); i >= 1; i--){
        drvo[i] = drvo[2 * i] + drvo[2 * i + 1];
        drvogore[i] = drvogore[2 * i] + drvogore[2 * i + 1];
        drvodole[i] = drvodole[2 * i] + drvodole[2 * i + 1];
    }
    int q, vrsta, l, r, duzina;
    cin >> q;
    for(int upit = 0; upit < q; upit++){
        cin >> vrsta;
        if(vrsta == 1){
            vector<int>menjamo(k);
            for(int i = 0; i < k; i++){
                cin >> menjamo[i];
                menjamo[i] -= 1;
            }
            if (k > 1) {
                int prvi = drvo[dva + menjamo[0]];
                for(int i = 0; i < (k - 1); i++) {
                    drvo[dva + menjamo[i]] = drvo[dva + menjamo[i + 1]];
                }
                drvo[dva + menjamo[k - 1]] = prvi;
                for(int i = 0; i < k; i++) {
                    drvogore[dva + menjamo[i]] = drvo[dva + menjamo[i]] * (menjamo[i] + 1);
                    drvodole[dva + menjamo[i]] = drvo[dva + menjamo[i]] * (n - menjamo[i]);
                }
                for(int i = 0; i < k; i++) {
                    int tr = dva + menjamo[i];
                    tr /= 2;
                    while (tr) {
                        drvo[tr] = drvo[2 * tr] + drvo[2 * tr + 1];
                        drvogore[tr] = drvogore[2 * tr] + drvogore[2 * tr + 1];
                        drvodole[tr] = drvodole[2 * tr] + drvodole[2 * tr + 1];
                        tr /= 2;
                    }
                }
            }
        }
        else{
            cin >> l >> r >> duzina;
            l -= 1;
            r -= 1;
            int tl = dva, tr = m - 1, u = 1;
            if(2 * duzina < (r - l + 1)){
                ll levo = -zbir(l + dva, l + duzina - 1 + dva, drvo, tl, tr, u) * l;
                tl = dva, tr = m - 1, u = 1;
                levo += zbir(l + dva, l + duzina - 1 + dva, drvogore, tl, tr, u);
                tl = dva, tr = m - 1, u = 1;
                ll desno = -zbir(r - duzina + 1 + dva, r + dva, drvo, tl, tr, u) * (n - r - 1);
                tl = dva, tr = m - 1, u = 1;
                desno += zbir(r + 1 - duzina + dva, r + dva, drvodole, tl, tr, u);
                tl = dva, tr = m - 1, u = 1;
                ll sredina = zbir(l + duzina + dva, r - duzina + dva, drvo, tl, tr, u) * duzina;
                cout << levo + sredina + desno << endl;
            }
            else{
                int kraj = r - duzina;
                int duzina1 = kraj - l + 1;
                ll levo = -zbir(l + dva, l + duzina1 - 1 + dva, drvo, tl, tr, u) * l;
                tl = dva, tr = m - 1, u = 1;
                levo += zbir(l + dva, l + duzina1 - 1 + dva, drvogore, tl, tr, u);
                tl = dva, tr = m - 1, u = 1;
                ll desno = -zbir(r - duzina1 + 1 + dva, r + dva, drvo, tl, tr, u) * (n - r - 1);
                tl = dva, tr = m - 1, u = 1;
                desno += zbir(r - duzina1 + 1 + dva, r + dva, drvodole, tl, tr, u);
                tl = dva, tr = m - 1, u = 1;
                ll sredina = zbir(l + duzina1 + dva, r - duzina1 + dva, drvo, tl, tr, u) * (duzina1 + 1);
                cout << levo + sredina + desno << endl;
            }
        }
    }
}

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8