oj.uz

Submission #1031536

# Submission time Handle Problem Language Result Execution time Memory
1031536 2024-07-23T00:03:15 Z AndiR Addk (eJOI21_addk) C++14
100 / 100
 73 ms 8272 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], neww[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)%k];
        ll delta=w[nxtind]-w[ind];

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

        neww[i]=w[nxtind];
    }
    for (int i=0; i<k; i++)
        w[perm[i]]=neww[i];
}
inline ll calculate(){
    int d=r-l+1;
    if (m>d/2)
        m=d-m+1;
    ll sum=0;
    sum+=aiblinc.sum(l, l+m-1)-aibdel.sum(l, l+m-1)*(l-1);
    sum+=aiblind.sum(r-m+1, r)-aibdel.sum(r-m+1, r)*(n-r);
    if (d%2==1 && m==d/2+1)
        sum-=(ll)w[l+m-1]*m;
    else sum+=aibdel.sum(l+m, 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
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 576 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 616 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 4 ms 1112 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1628 KB Output is correct
2 Correct 12 ms 2396 KB Output is correct
3 Correct 16 ms 2896 KB Output is correct
4 Correct 30 ms 4956 KB Output is correct
5 Correct 42 ms 6992 KB Output is correct
6 Correct 44 ms 6756 KB Output is correct
7 Correct 42 ms 6996 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4180 KB Output is correct
2 Correct 40 ms 5972 KB Output is correct
3 Correct 73 ms 8272 KB Output is correct
4 Correct 47 ms 7588 KB Output is correct