Submission #833673

#	Time	Username	Problem	Language	Result	Execution time	Memory
833673		dshfjka	Addk (eJOI21_addk)	C++14	100 / 100	277 ms	15708 KiB

Main

#include <bits/stdc++.h>
#define LL long long
#define mp make_pair
#define fi first
#define se second
#define int long long
using namespace std;
LL n;
const LL maxn=1e5+5;
LL arr[maxn+5];
struct Segtree {
   	LL inc[4*maxn+5],dec[4*maxn+5],sum[4*maxn+5];
	LL N;
	void init(LL x)
	{
	//	printf("SININININ\n");
		N=x;
	//	printf("N=%lld\n",N);
	}
    LL combine(LL x, LL y) {
        return x+y;
    }

    void build(int v, int s, int e) {
   // 	printf("%lld %lld %lld\n",v,s,e);
        if (s == e) {
            sum[v] =arr[s];
            inc[v]=arr[s]*s;
            dec[v]=arr[s]*(N+1-e);
         //   printf("%lld=%lld*(%lld+1-%lld)\n",dec[v],arr[s],N,e);
        } else {
            int mid = (s + e) >> 1;
            build(v << 1, s, mid);
            build(v << 1 | 1, mid + 1, e);
            sum[v] = combine(sum[v << 1], sum[v << 1 | 1]);
          	inc[v] = combine(inc[v << 1], inc[v << 1 | 1]);
          	dec[v] = combine(dec[v << 1], dec[v << 1 | 1]);
        //  	printf("dec[%lld]=%lld\n",v,dec[v]);
        }
    //    printf("t[%lld]=%lld\n",v,t[v]);
    }
    
    pair<LL,pair<LL,LL>> get(int v, int s, int e, int l, int r) {
        if (e < l || s > r || l > r)
            return make_pair(0LL,mp(0,0));
        if (l <= s && e <= r)
            return mp(sum[v],mp(inc[v],dec[v]));
        int mid = (s + e) >> 1;
        auto p1 = get(v << 1, s, mid, l, r);
        auto p2 = get(v << 1 | 1, mid + 1, e, l, r);
       	LL temp =combine(p1.fi, p2.fi);
       	LL temp2=combine(p1.se.fi,p2.se.fi);
       	LL temp3=combine(p1.se.se,p2.se.se);
       	return mp(temp,mp(temp2,temp3));
    }
    void update(LL v, LL l, LL r,LL x,LL idx)
    {
    	if( l==r){
    		sum[v] =idx;
            inc[v]=idx*l;
            dec[v]=idx*(N+1-r);
    	//	printf("x=%lld t[%lld]=%lld\n",x,v,t[v]);
    		return;
		}
		LL mid=(l+r)/2;
		if(x<=mid)update(v<<1,l,mid,x,idx);
		else update(v<<1 |1,mid+1,r,x,idx);
		sum[v] = combine(sum[v << 1], sum[v << 1 | 1]);
        inc[v] = combine(inc[v << 1], inc[v << 1 | 1]);
        dec[v] = combine(dec[v << 1], dec[v << 1 | 1]);
	}
};
signed main()
{
	LL n,k;
	scanf("%lld %lld",&n,&k);
	Segtree s;
	for(LL a=1;a<=n;a++)
	{
		scanf("%lld",&arr[a]);	
	}
	s.init(n);
	s.build(1,1,n);
	
	LL q;
	scanf("%lld",&q);
	while(q--)
	{
		LL type;
		scanf("%lld",&type);
		if(type==1)
		{
			LL temp[k+5];
			for(LL x=1;x<=k;x++)
			{
				LL y;
				scanf("%lld",&y);
				temp[x]=y;
			}
			LL dorr=temp[1];
			LL dor=arr[temp[1]];
			for(LL x=1;x<=k;x++)
			{
				if(x!=k)
				{
					arr[temp[x]]=arr[temp[x+1]];
					s.update(1,1,n,temp[x],arr[temp[x]]);
				}
				else
				{
					arr[temp[x]]=dor;
					s.update(1,1,n,temp[x],dor);
				 } 
			}
//			for(LL a=1;a<=n;a++)printf("%lld ",arr[a]);
//			cout<<endl;
		}
		else
		{
			// sum increment decrement
			LL l,r,m;
			scanf("%lld %lld %lld",&l,&r,&m);
			LL ans=0;
			if(l+m-1<r-m+1)
			{
				
				// dia tidak bersinggungan 
			//	printf("SINI\n");
				ans+=s.get(1,1,n,l,l+m-2).se.fi-s.get(1,1,n,l,l+m-2).fi*(l-1);
		//		printf("ans1= %lld\n",ans);
				ans+=s.get(1,1,n,l+m-1,r-m+1).fi*m;
			//	printf("ans2 = %lld\n",ans);
				ans+=s.get(1,1,n,r-m+2,r).se.se-s.get(1,1,n,r-m+2,r).fi*(n-r);
			//	printf("ans3= %lld-%lld*%lld\n",s.get(1,1,n,r-m+2,r).se.se,s.get(1,1,n,r-m+2,r).fi,(n-r));
			}
			else
			{
			//	printf("MASUK\n");
				ans+=s.get(1,1,n,l,r-m).se.fi-s.get(1,1,n,l,r-m).fi*(l-1);
			//	printf("ans1=%lld-%lld*%lld\n",s.get(1,1,n,l,r-m).se.fi,s.get(1,1,n,l,r-m).fi,(l-1));
			//	printf("ans1= %lld\n",ans);
				ans+=s.get(1,1,n,r-m+1,l+m-1).fi*(r-l-m+2);
		//		printf("ans2+=%lld*%lld=%lld\n",s.get(1,1,n,r-m+1,l+m-1).fi,(r-l-m+2),ans);
				ans+=s.get(1,1,n,l+m,r).se.se-s.get(1,1,n,l+m,r).fi*(n-r);
		//		printf("ans3=%lld-%lld*%lld\n",s.get(1,1,n,l+m,r).se.se,s.get(1,1,n,l+m,r).fi,(n-r));
			}
			printf("%lld\n",ans);
		}
	}
	
	
	
	
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:100:7: warning: unused variable 'dorr' [-Wunused-variable]
  100 |    LL dorr=temp[1];
      |       ^~~~
Main.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%lld %lld",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%lld",&arr[a]);
      |   ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  scanf("%lld",&q);
      |  ~~~~~^~~~~~~~~~~
Main.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf("%lld",&type);
      |   ~~~~~^~~~~~~~~~~~~~
Main.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%lld",&y);
      |     ~~~~~^~~~~~~~~~~
Main.cpp:122:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |    scanf("%lld %lld %lld",&l,&r,&m);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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