oj.uz

Submission #1031523

# Submission time Handle Problem Language Result Execution time Memory
1031523 2024-07-22T23:26:26 Z AndiR Addk (eJOI21_addk) C++14
0 / 100
 31 ms 4188 KB 
// Author: Tanasescu Andrei-Rares
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#include <cassert>

#pragma GCC optimize("O3")

#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;

ifstream fin ("addk.in");
ofstream fout ("addk.out");

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll Nmax=1e5+5, inf=1e9+5, Kmax=10;

int n, q, k, cer, l, r, m;
int w[Nmax], perm[Kmax];

struct AIB{
    ll v[Nmax];

    inline ll _sum(int pos){
        ll sum=0;
        while (pos!=0){
            sum+=v[pos];
            pos-=pos&-pos;
        }
        return sum;
    }
    inline ll sum(int l, int r){
        return _sum(r)-_sum(l-1);
    }
    inline void update(int pos, ll val){
        while (pos<=n){
            v[pos]+=val;
            pos+=pos&-pos;
        }
    }
    inline void build(bool lin, bool cresc){
        for (int i=1; i<=n; i++){
            if (lin)
                if (cresc)
                    v[i]+=(ll)i*w[i];
                else v[i]+=(ll)(n-i+1)*w[i];
            else v[i]+=w[i];

            int j=i+(i&-i);
            if (j<=n)
                v[j]+=v[i];
        }
    }
}aiblinc, aiblind, aibdel;

inline void permutate(){
    for (int i=0; i<k; i++){
        int ind=perm[i];
        int nxtind=perm[(i+1)%n];
        ll delta=w[nxtind]-w[ind];

        aiblinc.update(ind, delta*ind);
        aiblind.update(ind, delta*(n-ind+1));
        aibdel.update(ind, delta);

        w[ind]+=delta;
    }
}
inline ll calculate(){
    if (m>n/2)
        m=n-m+1;
    ll sum=0;
    sum+=aiblinc.sum(l, m)-aibdel.sum(l, m)*(l-1);
    sum+=aiblind.sum(r-m+1, r)-aibdel.sum(r-m+1, r)*(n-r);
    if (n%2==1 && m==n/2+1)
        sum-=(ll)w[l+m-1]*m;
    else sum+=aibdel.sum(m+1, r-m)*m;

    return sum;
}

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

    cin>>n>>k;
    for (int i=1; i<=n; i++)
        cin>>w[i];

    aiblinc.build(1, 1);
    aiblind.build(1, 0);
    aibdel.build(0, 0);

    cin>>q;

    while (q--){
        cin>>cer;
        if (cer==1){
            for (int i=0; i<k; i++)
                cin>>perm[i];
            permutate();
        }
        else{
            cin>>l>>r>>m;
            cout<<calculate()<<'\n';
        }
    }

    return 0;
}

Subtask #1
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 4188 KB Output isn't correct
2 Halted 0 ms 0 KB -