Submission #1031225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031225		Dennis_Jason	Addk (eJOI21_addk)	C++14	100 / 100	405 ms	15700 KiB

Main

#include <bitset>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#define int long long
#define pb push_back
#define MOD 1000000007
#define NMAX 100005
#define nl '\n'
#define INF 1000000007
#define pii1 pair<int, pair<int,int>>  (1,(1,2));
#define pii pair<int,int>
#define tpl tuple<int,int,int>
using namespace std;
ifstream fin("data.in");
ofstream fout("data.out");
struct item{
    int sum,pref,suf;
};
class segtree{
private:
    int n;
    vector<item>tree;
public:
    void init(int sz)
    {
        n=sz;
        tree.resize(4*sz+1);
    }
    item single(int val,int pos)
    {
        return{
            val,
            pos*val,
            (n-pos+1)*val
        };
    }
    item calc(item a,item b)
    {
        return{
            a.sum+b.sum,
            a.pref+b.pref,
            a.suf+b.suf
        };
    }
    void update(int node,int st,int dr,int pos,int val)
    {
        if(st==dr)
        {
            tree[node]=single(val,st);
            return;
        }
        int mid=(st+dr)/2;
        if(pos<=mid)
            update(2*node,st,mid,pos,val);
        else
            update(2*node+1,mid+1,dr,pos,val);
        tree[node]=calc(tree[2*node],tree[2*node+1]);
    }
    item query(int node,int st,int dr,int L,int R)
    {
        if(R<st || dr<L)
            return {0,0,0};
        if(L<=st && dr<=R)
        {
            return tree[node];
        }
        int mid=(st+dr)/2;
        item left=query(2*node,st,mid,L,R);
        item right=query(2*node+1,mid+1,dr,L,R);
        return calc(left,right);
    }
    void update(int pos,int val)
    {
        update(1,1,n,pos,val);
    }
    item query(int L,int R)
    {
        return query(1,1,n,L,R);
    }
};

/*
 *
 *
    ------EXAMPLE-----
    1 2 3 4 5 6 7 8
    7 2 5 1 9 3 4 6
    2 2 7 4

    m=4, length=6
    2 5 1 9 3 4

    2+5+1+9=17
    5+1+9+3=18
    1+9+3+4=17

    2*1,5*2,1*3,9*3,3*2,4*1

    m=min(4,6-4+1)
    m=min(4,3)
    m=3;
    x=(l+m-1)=2+3-1=4
    y=5

    3*2+4*1=10
    3+4=7
    3*3+4*2=17

    ---------DEMONSTRATION------------
    m=min(m,(r-l+1)-m+1)
    m=min(12,(20-5+1)-12+1)
    m=min(12,(15+1)-12+1)
    m=min(12,(16-12+1))
    m=min(12,5),5
    5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
elm 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
   20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5

    1 2 3 4 5  6  7  8  9 10 11 12=78
    2 3 4 5  6  7  8  9 10 11 12 13=90
    3 4 5  6  7  8  9 10 11 12 13 14=102
    4 5  6  7  8  9 10 11 12 13 14 15=114
    5  6  7  8  9 10 11 12 13 14 15 16=126
    total                             =510

    1*1,2*2,3*3,4*4,5*5,6*5,7*5,8*5,9*5,10*5,11*5,12*5,13*4,14*3,15*2,16*1 ->> max freq is new m

    x=(l+m-1)=5+5-1=9
    y=(r-m+1)=20-5+1=16 from x to y is maxim freq
   1. First is sum(x,y).sum*m=68*m=340;

    I need to find sum from (l,x-1) and(y+1,r)

    Sum(l,x-1)
    ind:5 6 7 8
    1*1,2*2,3*3,4*4/ this is here, is the elem * ind, but the real ind is 5,6,7,8
    1*5,2*6,3*7,4*8
    1*20,2*18,3*17,4*16

    let's calculate:
    i need  1+4+9+16=30
    1+2+3+4=10*(5-1)=40
    5+12+21+32=17+53=70-40=30 this is true

    Second sum is sum(l,x-1).pref-sum(l,x-1).sum*(l-1)

    SUM(y+1,r)
    ind:17 18 19 20
    i need:13*4+14*3+15*2+16*1=140
    13+14+15+16=30+28=58


    Third sum(y+1,r).suf-sum(y+1,r)*(n-r)



 */
segtree st;
void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int>v(n+1);
    st.init(n);
    for(int i=1;i<=n;++i)
    {
        cin>>v[i];
        st.update(i,v[i]);
    }
    int q;
    cin>>q;
    while(q--)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            vector<int>ind(k+1);
            for(int i=1;i<=k;++i)
                cin>>ind[i];
            // v[ind[1]]=v[ind[2]]
            //...................
            ///v[ind[k]]=v[ind[1]]
            vector<int>val(k+1);
            for(int i=1;i<=k;++i)
            {
                val[i]=st.query(ind[i],ind[i]).sum;
            }
            for(int i=1;i<k;++i)
            {
                st.update(ind[i],val[i+1]);
            }
            st.update(ind[k],val[1]);
        }
        else
        {
            int l,r,m;
            cin>>l>>r>>m;
            m=min(m,(r-l+1)-m+1);
            int x=(l+m-1);
            int y=(r-m+1);
            int ans=0;
            item sum1=st.query(l,x-1);
            item sum2=st.query(x,y);
            item sum3=st.query(y+1,r);
            ans+=(sum1.pref-sum1.sum*(l-1));
            ans+=(sum2.sum*m);
            ans+=(sum3.suf-sum3.sum*(n-r));
            cout<<ans<<nl;
        }
    }

}
signed main() {

    int t=1;
//    cin>>t;
    while(t--)
        solve();

    return 0;
}

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8