oj.uz

Submission #638042

# Submission time Handle Problem Language Result Execution time Memory
638042 2022-09-04T11:22:15 Z Vovamatrix Addk (eJOI21_addk) C++14
92 / 100
 72 ms 6568 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 if(r-l+1<2*m) 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);
            else rez=m*bit.get(l+m-1,r-m+1)+bit1.get(l,l+m-2)+(r+1)*bit.get(r-m+2,r)-(l-1)*bit.get(l,l+m-2)-bit1.get(r-m+2,r);
            cout<<rez<<endl;
        }
    }
    return 0;
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 5 ms 724 KB Output is correct
9 Correct 7 ms 856 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1112 KB Output is correct
2 Correct 20 ms 2136 KB Output is correct
3 Correct 23 ms 2808 KB Output is correct
4 Correct 43 ms 4752 KB Output is correct
5 Correct 59 ms 6568 KB Output is correct
6 Correct 72 ms 6348 KB Output is correct
7 Correct 62 ms 6312 KB Output is correct

Subtask #3
0 / 8.0

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