Submission #581593

#	Time	Username	Problem	Language	Result	Execution time	Memory
581593		TimDee	Addk (eJOI21_addk)	C++14	100 / 100	1310 ms	12296 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define paiu return
#define moment 0;
 
#define int long long
#define ll long long
 
#define forr(i,x) for (int i=0; i<x; i++)
#define forn(i,x) for (int i=0; i<x; i++)
#define forrr(i,j,x) for (int i=j; i<x; i++)
 
#define di(a,n) deque<int> a(n,0)
#define dll(a,n) deque<ll> a(n,0)
#define vi(a,n) vector<int> a(n,0)
#define vll(a,n) vector<ll> a(n,0)
 
//cringe define
#define vii(a,n) vi(a,n); forr(i,n) cin>>a[i];
vector<int> ___makeprefsum(vector<int>&a) {
    int n=a.size();
    vi(pr,n+1);
    forn(i,n) pr[i+1]=pr[i]+a[i];
    return pr;
}
#define prefsum(pr,a) vector<int> pr=___makeprefsum(a);

#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
 
#define pb(x) push_back(x)
#define pf pop_front();
#define last(c) c[c.size()-1]
 
#define f first
#define s second
 
#define pi pair<int, int>
#define mp(x,y) make_pair(x, y)
 
const ll mod = 1000000007;
const double ppi = acos(0) * 2;
     
//const int maxn = 3e5+1;
const int inf = INT_MAX;
const ll linf = LLONG_MAX;
const ll mmod = 998244353;

struct segtree {
    
    vector<int> tree;
    vector<pi> addtree;
    int size;
    int n;
    int neutral;
    
    void put(int i, int v) {
        
        tree[i]=v;
        addtree[i]={v,1};
        
    }
    
    int combine(int i, int j) {
        //for min
        //return min(i,j);
        //for max
        //return max(i,j);
        //for sum
        return i+j;
    }

    pi addcombine(pi a, pi b, int lb, int rb) {
        return {a.f+(b.s!=0)*a.s*query(lb,rb)+b.f,a.s+b.s};
    }
 
    void update(int x, int l, int r, int i) {
        
        if (i>=r || i<l) return;
        if (r-l == 1) return;
        
        int mid=(l+r)/2;
        update(2*x+1,l,mid,i);
        update(2*x+2,mid,r,i);
        
        tree[x]=combine(tree[2*x+1],tree[2*x+2]);
        addtree[x]=addcombine(addtree[2*x+1],addtree[2*x+2],mid,r);
    }
    
    void update(int x, int l, int r) {
 
        if (r-l == 1) return;
        
        int mid=(l+r)/2;
        update(2*x+1,l,mid);
        update(2*x+2,mid,r);
        
        tree[x]=combine(tree[2*x+1],tree[2*x+2]);
        addtree[x]=addcombine(addtree[2*x+1],addtree[2*x+2],mid,r);
    }
    
    segtree(vector<int>&a, int neutr) {
        
        n=a.size();
       
        //for min
        //neutral = inf;
        //for max
        //neutral = -inf;
        //for sum
        //neutral = 0;

        neutral = neutr;

        size=1;
        while (size < n) size*=2;
        
        tree.assign(2*size-1,neutral);
        addtree.assign(2*size-1,{neutral,0});
        
        forr(i,n) put(size-1+i,a[i]);
        
        update(0,0,size);
        
    }
    
    void clear() {
        
        tree.assign(2*size-1,0);
        
    }
    
    int calc(int x, int lx, int rx, int l, int r) {
        
        if (lx>=r || rx<=l) return neutral;
        if (lx>=l && rx<=r) return tree[x];
        
        int mid=(lx+rx)/2;
        int a=calc(2*x+1,lx,mid,l,r),
        b=calc(2*x+2,mid,rx,l,r);
        return combine(a,b);
    }
    
    int query(int l, int r) {
        if (l>=r) return neutral;
        return calc(0,0,size,l,r);
    }

    pi addquery(int x, int lx, int rx, int l, int r) {
        
        if (lx>=r || rx<=l) return {neutral,0};
        if (lx>=l && rx<=r) return addtree[x];
        
        int mid=(lx+rx)/2;
        pi a=addquery(2*x+1,lx,mid,l,r),
        b=addquery(2*x+2,mid,rx,l,r);

        pi k = addcombine(a,b,mid,mid+b.s);
        //cout<<lx<<' '<<rx<<":\n";
        //cout<<a.f<<' '<<a.s<<'\n';
        //cout<<b.f<<' '<<b.s<<'\n';
        //cout<<k.f<<' '<<k.s<<'\n';
        return k;
    }

    int addquery(int l, int r) {
        pi k = addquery(0,0,size,l,r);
        //cout<<k.f<<' '<<k.s<<'\n';
        return k.f;
    }
    
    void set(int i, int v) {
        
        put(size-1+i,v);
        update(0, 0, size, i);
        
    }
    
    void print() {
        
        cout<<"TREE: \n";
        int z=0;
        while (z<addtree.size()) {
            for (int i=z; i<2*z+1; i++) cout<<addtree[i].f<<' ';
            cout<<'\n';
            z=z*2+1;
        }
        cout<<'\n';
        
    }
    
};

void solve() {
    
    int n,k; cin>>n>>k;
    vii(a,n);

    vector<int> b=a;

    segtree st(a,0);

    int m; cin>>m;

    //st.print();

    forn(Q,m) {

        int q; cin>>q;
        if (q==1) {
            vector<int> v(k);
            forn(i,k) cin>>v[i];
            forn(i,k) {
                b[v[i]-1]=a[v[(i+1)%k]-1];
            }
            forn(i,k) {
                st.set(v[i]-1,b[v[i]-1]);
            }
            forn(i,k) a[v[i]-1]=b[v[i]-1];
            //forn(i,n) cout<<a[i]<<' '; cout<<'\n';
        } else {
            int l,r,m; cin>>l>>r>>m;
            int L,R;
            int res=0;
            if ((r+1-l)%2) {
                if (l-1+(r+1-l)/2<l+m-2) {
                    L=r-m;
                } else {
                    L=l+m-2;
                }
                R=r-(L+1-l);
            } else {
                if (l-1+(r+1-l)/2<l+m-2) {
                    L=r-m;
                } else {
                    L=l+m-2;
                }
                R=r-(L+1-l);
            }
            //cout<<"["<<l-1<<","<<L<<") ["<<R<<','<<r<<") ";
            res+=st.addquery(l-1,L);
            //cout<<" | "<<res<<" | ";
            res+=1ll*min(L+2-l,m)*st.query(L,r);
            //cout<<" | "<<res<<" | ";
            res-=st.addquery(R,r);
            //cout<<" | "<<res<<" | ";
            cout<<res<<'\n';
        }

    }

}

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

    //init_primes();
    
    int t=1;
    //cin>>t;
    
    while(t--) solve();
    
    paiu moment
}

Compilation message (stderr)

Main.cpp: In member function 'void segtree::print()':
Main.cpp:184:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |         while (z<addtree.size()) {
      |                ~^~~~~~~~~~~~~~~

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