Submission #684180

#	Time	Username	Problem	Language	Result	Execution time	Memory
684180		Victor	Addk (eJOI21_addk)	C++17	100 / 100	386 ms	18440 KiB

Main

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int arr[1'000'005],n,k;

struct Node {
    int lo,hi;
    ll sum,inc_sum,dec_sum;
    Node *l,*r;

    Node(int L,int R) : lo(L),hi(R) {
        if(lo+1==hi) sum=inc_sum=dec_sum=arr[lo];
        else {
            int mid=(lo+hi)/2;
            l=new Node(lo,mid);
            r=new Node(mid,hi);
            merge();
        }
    }

    pair<ll,pll> query(int L,int R,int type) {
        if(hi<=L||R<=lo) return {0,{0,0}};
        if(L<=lo&&hi<=R) {
            if(type==0) return {sum,{hi-lo,sum}};
            if(type==1) return {inc_sum,{hi-lo,sum}};
            if(type==2) return {dec_sum,{hi-lo,sum}};
        }
        int lvals,rvals;
        ll lsum,rsum,lsum1,rsum1;

        auto a=l->query(L,R,type);
        auto b=r->query(L,R,type);

        lsum1=a.first;
        rsum1=b.first;

        tie(lvals,lsum)=a.second;
        tie(rvals,rsum)=b.second;

        /*if(type==1) {
            cout<<"lo = "<<lo<<" hi = "<<hi<<endl;
            cout<<"lsum = "<<lsum1<<" rsum = "<<rsum1<<" lvals = "<<lvals<<" rvals = "<<rvals<<endl;
            cout<<"sum = "<<lsum+rsum<<endl<<endl;
        }*/

        if(type==0) return {lsum1+rsum1,{lvals+rvals,lsum+rsum}};
        if(type==1) return {lsum1+rsum1+rsum*lvals,{lvals+rvals,lsum+rsum}};
        if(type==2) return {lsum1+rsum1+lsum*rvals,{lvals+rvals,lsum+rsum}};
    }

    void set(int x,int pos) {
        if(hi<=pos||pos<lo) return;
        if(lo+1==hi) {
            sum=inc_sum=dec_sum=x;
            //cout<<"x = "<<x<<" pos = "<<pos<<" lo = "<<lo<<" hi = "<<hi<<endl;
            return;
        }
        l->set(x,pos);
        r->set(x,pos);
        merge();
        //cout<<"lo = "<<lo<<" hi = "<<hi<<" sum = "<<sum<<" inc_sum = "<<inc_sum<<" dec_sum = "<<dec_sum<<endl;
    }

    void merge() {
        int mid=(lo+hi)/2;
        int lvals=mid-lo,rvals=hi-mid;
        sum=l->sum+r->sum;
        inc_sum=l->inc_sum+r->inc_sum+r->sum*lvals;
        dec_sum=l->dec_sum+r->dec_sum+l->sum*rvals;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int indexes[10]; 
    cin>>n>>k;
    rep(i,0,n) cin>>arr[i];
    Node segtree(0,n);
    int q;
    cin>>q;
    while(q--) {
        int type;
        cin>>type;
        if(type==1) {
            rep(i,0,k) cin>>indexes[i],--indexes[i];
            rep(i,0,k-1) swap(arr[indexes[i]],arr[indexes[i+1]]);
            rep(i,0,k) segtree.set(arr[indexes[i]],indexes[i]);//cout<<"index = "<<indexes[i]<<" val = "<<arr[indexes[i]]<<endl;
            //rep(i,0,n) cout<<arr[i]<<' ';
            //cout<<endl<<endl;

        } else {
            int lo,hi,m;
            cin>>lo>>hi>>m;
            --lo;
            int mx=min(hi-lo-m+1,m);

            //cout<<"mx = "<<mx<<' '<<hi-lo-m<<endl;
            //segtree.query(lo,lo+mx-1,1);
            //cout<<segtree.query(lo,lo+mx-1,1).first<<' '<<segtree.query(lo,lo+mx-1,1).second.first<<endl;
            //cout<<segtree.query(lo+mx-1,hi-mx+1,0).first<<' '<<segtree.query(lo+mx-1,hi-mx+1,0).second.first<<endl;
            //cout<<segtree.query(hi-mx+1,hi,2).first<<' '<<segtree.query(hi-mx+1,hi,2).second.first<<endl;
            //
            cout<<segtree.query(lo,lo+mx-1,1).first+segtree.query(lo+mx-1,hi-mx+1,0).first*mx+segtree.query(hi-mx+1,hi,2).first<<'\n';
            //break;
        }
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'std::pair<long long int, std::pair<long long int, long long int> > Node::query(int, int, int)':
Main.cpp:78:5: warning: control reaches end of non-void function [-Wreturn-type]
   78 |     }
      |     ^

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