oj.uz

Submission #638039

# Submission time Handle Problem Language Result Execution time Memory
638039 2022-09-04T11:10:21 Z Vovamatrix Addk (eJOI21_addk) C++14
0 / 100
 45 ms 3820 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define PI acos(-1)
#define LSB(i) ((i) & -(i))
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define sc second
#define th third
#define fo fourth
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
#define MOD 1000000007
#define endl "\n"

#define all(data)       data.begin(),data.end()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()
#define ima_li_te(D,d)  find(all(D),d)
#define MAXN 100007
ll a[MAXN],b[20];
struct Fenwick
{
    vector<ll> BIT;
    ll n;
    void init(ll x) {n=x; BIT.assign(n+1,0);}
    ll psum(ll x)
    {
        ll rez=0; x++;
        for(ll i=x;i>0;i-=LSB(i)) rez+=BIT[i];
        return rez;
    }
    ll get(ll x,ll y)
    {
        if(x<=y) return psum(y)-psum(x-1);
        else return 0;
    }
    void add(ll x,ll d)
    {
        x++;
        for(ll i=x;i<=n;i+=LSB(i)) BIT[i]+=d;
    }
};
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    ll n,k; cin>>n>>k;
    Fenwick bit,bit1;
    bit.init(n+3); bit1.init(n+3);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) {bit.add(i,a[i]); bit1.add(i,i*a[i]);};
    ll q,x,l,r,m;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>x;
        if(x==1)
        {
            for(int i=0;i<k;i++) cin>>b[i];
            for(int i=0;i<k;i++)
            {
                bit.add(b[i],a[b[(i+1)%k]]-a[b[i]]);
                bit1.add(b[i],b[i]*(a[b[(i+1)%k]]-a[b[i]]));
                a[b[i]]=a[b[(i+1)%k]];
            }
        }
        else
        {
            cin>>l>>r>>m;
            ll rez=0;
            if(m==r-l+1) rez=bit.get(l,r);
            else rez=(r-l-m+2)*bit.get(r-m+1,l+m-1)+bit1.get(l,r-m)+(r+1)*bit.get(l+m,r)-(l-1)*bit.get(l,r-m)-bit1.get(l+m,r);
            //cout<<(r-l-m+2)*bit.get(r-m+1,l+m-1)<<" "<<bit1.get(l,r-m)-(l-1)*bit.get(l,r-m)<<" "<<(r+1)*bit.get(l+m,r)-bit1.get(l+m,r)<<endl;
            cout<<rez<<endl;
        }
    }
    return 0;
}

Subtask #1
0 / 36.0

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

Subtask #2
0 / 56.0

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

Subtask #3
0 / 8.0

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