oj.uz

Submission #633762

# Submission time Handle Problem Language Result Execution time Memory
633762 2022-08-23T08:17:06 Z giorgikob Addk (eJOI21_addk) C++14
100 / 100
 184 ms 8020 KB 
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define count1(x) __builtin_popcount(x)
#define endl '\n'
using namespace std;

const int N = 1e6+1, mod = 1e6, K = 31;

int n, k, q;
ll tree[N][2], A[N];

void upd(ll val, int pos, int k){
    while(pos < N){
        tree[pos][k] += val;
        pos += (pos & -pos);
    }
}

ll get(int pos, int k){
    ll res = 0;
    while(pos > 0){
        res += tree[pos][k];
        pos -= (pos & -pos);
    }

    return res;
}

ll range_query(int l, int r, int k){
    return get(r, k) - get(l-1, k);
}

inline void test_case(){

    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> A[i];
        upd(A[i], i, 0);
        upd((ll)A[i]*i, i, 1);
    }

    cin >> q;
    while(q--){
        int type;
        cin >> type;
        if(type == 1){
            int ind[k];
            for(int i = 0; i < k; i++){
                cin >> ind[i];
            }
            int first = A[ind[0]];
            for(int i = 0; i < k; i++){
                int a = ind[i], b = ind[(i+1)%k];
                ll vala = A[a];
                ll valb = A[b];
                if(i < k-1) {
                    A[a] = A[b];
                } else {
                    valb = first;
                    A[a] = first;
                }
                upd(valb - vala, a, 0);
                upd((valb - vala)*a, a, 1);
            }
        } else {
            int l, r, m;
            cin >> l >> r >> m;
            int mid = (l+r)/2;
            int l1 = 0;
            int r1 = 0;
            if((r-l+1) < m*2-1){
                m = (r-l+1) - m + 1;
            }
            l1 = l+m-1;
            r1 = r-m+1;
            ll res1 = range_query(l, l1-1, 1) - (l-1)*range_query(l, l1-1, 0);
            //cout << res1 << endl;
            ll res2 = range_query(l1, r1, 0) * m;
            ll res3 = range_query(r1+1, r, 1) - (r1)*range_query(r1+1, r, 0);
            res3 = (r-r1+1)*range_query(r1+1, r, 0) - res3;
            //cout << res3 << endl;

            cout << res1 + res2 + res3 << endl;

            /*ll answer = 0;
            for(int i = l; i <= r-m+1; i++){
                for(int j = i; j <= i+m-1; j++){
                    answer += A[j];
                }
            }
            cout << answer << endl;
            assert(answer == res1 + res2 + res3);*/
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    //cin.tie(0); cout.tie(0);

    int T = 1;
    //cin >> T;
    while(T--){
        test_case();
    }
}

Compilation message

Main.cpp: In function 'void test_case()':
Main.cpp:74:17: warning: unused variable 'mid' [-Wunused-variable]
   74 |             int mid = (l+r)/2;
      |                 ^~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 7 ms 508 KB Output is correct
6 Correct 9 ms 664 KB Output is correct
7 Correct 11 ms 724 KB Output is correct
8 Correct 12 ms 736 KB Output is correct
9 Correct 17 ms 944 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1576 KB Output is correct
2 Correct 53 ms 2208 KB Output is correct
3 Correct 75 ms 2816 KB Output is correct
4 Correct 123 ms 4748 KB Output is correct
5 Correct 169 ms 6696 KB Output is correct
6 Correct 168 ms 6488 KB Output is correct
7 Correct 161 ms 6476 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 3824 KB Output is correct
2 Correct 147 ms 5728 KB Output is correct
3 Correct 169 ms 8020 KB Output is correct
4 Correct 184 ms 6960 KB Output is correct