Submission #1201769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201769		asli_bg	Addk (eJOI21_addk)	C++20	100 / 100	287 ms	10844 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#define int long long
 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<bool> vb;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<pll> vll;
 
typedef tree<pii,null_type,less<pii>,rb_tree_tag,
tree_order_statistics_node_update> oset;
 
#define fi first
#define se second
#define pb push_back
#define pf push_front
 
#define mid (l+r)/2
#define all(x) x.begin(),x.end()
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
 
#define cont(x) for(auto el:x) cout<<el<<' ';cout<<endl;
#define contp(x) for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;
#define sp <<" "<<
 
#define DEBUG(x) cout<<(#x) sp x<<endl
#define carp(a,b) (((a%MOD)*(b%MOD))%MOD)
#define topla(a,b) (((a%MOD)+(b%MOD))%MOD)
 
const ll INF=1e18;
const int MAXN=1e5+5;
const int MOD=1e9+7;

int n,k;
vi a;

pii t[4*MAXN];
pii t2[4*MAXN];
//t[nd]-->{istenen toplam,normal toplam}

void calc(int nd,int l,int r){
    //cout<<"segt" sp nd sp t[nd*2].fi sp t[nd*2].se sp t[nd*2+1].fi sp t[nd*2+1].se<<endl;
    t[nd].fi=(r-(mid+1)+1)*t[nd*2].se+t[nd*2].fi+t[nd*2+1].fi;
    t[nd].se=t[nd*2].se+t[nd*2+1].se;
    t2[nd].fi=(mid-l+1)*t2[nd*2+1].se+t2[nd*2].fi+t2[nd*2+1].fi;
    t2[nd].se=t2[nd*2].se+t2[nd*2+1].se;
}

void build(int nd=1,int l=1,int r=n){
    if(l==r){
        t[nd].fi=t[nd].se=t2[nd].fi=t2[nd].se=a[l];
        return;
    }

    build(nd*2,l,mid);
    build(nd*2+1,mid+1,r);

    calc(nd,l,r);
}

int q1(int ql,int qr,int nd=1,int l=1,int r=n){
    if(l>r or l>qr or r<ql) return 0;
    if(ql<=l and r<=qr){
        return t[nd].se;
    }
    auto s1=q1(ql,qr,nd*2,l,mid);
    auto s2=q1(ql,qr,nd*2+1,mid+1,r);
    return s1+s2;
}

vector<pair<pii,int>> vec;

void q2(int ql,int qr,int nd=1,int l=1,int r=n){
    if(l>r or l>qr or r<ql) return;
    if(ql<=l and r<=qr){
        vec.pb({{l,r},nd});
        return;
    }
    q2(ql,qr,nd*2,l,mid);
    q2(ql,qr,nd*2+1,mid+1,r);
}

void update(int pos,int val,int nd=1,int l=1,int r=n){
    if(l==r){
        t[nd].fi=t[nd].se=t2[nd].fi=t2[nd].se=val;
        return;
    }
    if(pos<=mid) update(pos,val,nd*2,l,mid);
    else update(pos,val,nd*2+1,mid+1,r);

    calc(nd,l,r);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k;
    a.resize(n+1);
    FORE(i,1,n+1) cin>>a[i];

    build();

    int q;
    cin>>q;

    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int el;
            vi tut;
            FOR(i,k){
                cin>>el;
                tut.pb(el);
            }

            int temp=a[tut[0]];
            FORE(i,1,k){
                update(tut[i-1],a[tut[i]]);
                a[tut[i-1]]=a[tut[i]];
            }
            update(tut[k-1],temp);
            a[tut[k-1]]=temp;
        }
        else{
            int l,r,m;
            cin>>l>>r>>m;

            int ara=r-l+1-m;
            int top=q1(l,r)*(ara+1);
            int cikar,cikar2;
            cikar=cikar2=0;

            pair<pii,int> cur;

            q2(l,l+ara-1);
            sort(all(vec));

            if(!vec.empty()){
                cur=vec[0];
                int tut=t[cur.se].se;
                cur.se=t[cur.se].fi;

                FORE(i,1,vec.size()){
                    int l=vec[i].fi.fi;
                    int r=vec[i].fi.se;
                    int nd=vec[i].se;

                    cur.se=cur.se+t[nd].fi+(r-l+1)*tut;
                    tut+=t[nd].se;
                    cur.fi.se=r;
                }

                cikar=cur.se;
                vec.clear();
            }

            /*********************************************** */

            q2(r-ara+1,r);
            sort(all(vec));

            if(!vec.empty()){
                cur=vec[0];
                cur.se=t2[cur.se].fi;

                FORE(i,1,vec.size()){
                    int l=vec[i].fi.fi;
                    int r=vec[i].fi.se;
                    int nd=vec[i].se;

                    cur.se=cur.se+t2[nd].fi+(cur.fi.se-cur.fi.fi+1)*(t2[nd].se);
                    cur.fi.se=r;
                }

                cikar2=cur.se;
                vec.clear();
            }   

            cout<<top-cikar-cikar2<<endl;
        }
    }
}

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