oj.uz

Submission #1110806

# Submission time Handle Problem Language Result Execution time Memory
1110806 2024-11-10T14:15:42 Z _rain_ Addk (eJOI21_addk) C++14
100 / 100
 202 ms 12360 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
#define name "main"
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)

const int N=(int)1'00'000;
int a[N+2];
int n,k,q;

#define lef(id) id<<1
#define rig(id) id<<1|1
LL st[N*4+2],lazy[N*4+2];
void pushdown(int id,int l,int r){
	int m=(l+r)>>1;
	LL &t=lazy[id];
	st[lef(id)]+=t*(m-l+1),lazy[lef(id)]+=t;
	st[rig(id)]+=t*(r-m),lazy[rig(id)]+=t;
	t=0;
	return;
}
void upd(int id,int l,int r,int u,int v,LL val){
	if (l>v||r<u) return;
	if (u<=l&&r<=v){
		st[id]+=val*(r-l+1);
		lazy[id]+=val;
		return;
	}
	int m=(l+r)>>1;
	pushdown(id,l,r);
	upd(lef(id),l,m,u,v,val);
	upd(rig(id),m+1,r,u,v,val);
	st[id]=st[lef(id)]+st[rig(id)];
}
LL Get(int id,int l,int r,int u,int v){
	if (l>v||r<u) return 0;
	if (u<=l&&r<=v) return st[id];
	int m=(l+r)>>1;
	pushdown(id,l,r);
	return Get(lef(id),l,m,u,v)+Get(rig(id),m+1,r,u,v);
}

void giai(){
	int t;cin>>t;
	if (t==1){
		vector<int>idx(k+2,0);
		vector<int>val(k+2,0);
		FOR(i,1,k) cin>>idx[i];
		idx[k+1]=idx[1];
		FOR(i,2,k+1){
			val[i-1]=a[idx[i]];
			upd(1,1,n,idx[i-1],n,a[idx[i]]-a[idx[i-1]]);
		}
		FOR(i,1,k) a[idx[i]]=val[i];
	}
	if (t==2)
	{
		int l,r,m;cin>>l>>r>>m;
		cout<<Get(1,1,n,l+m-1,r)-Get(1,1,n,l-1,r-m)<<'\n';
	}
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>k;
	FOR(i,1,n){
		cin>>a[i];
		upd(1,1,n,i,n,a[i]);
	}
	cin>>q;
	while(q--) giai();
	exit(0);
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 4600 KB Output is correct
3 Correct 3 ms 4432 KB Output is correct
4 Correct 4 ms 4688 KB Output is correct
5 Correct 5 ms 4688 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Correct 7 ms 4688 KB Output is correct
8 Correct 9 ms 4940 KB Output is correct
9 Correct 11 ms 6992 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7508 KB Output is correct
2 Correct 34 ms 7988 KB Output is correct
3 Correct 49 ms 8264 KB Output is correct
4 Correct 91 ms 9696 KB Output is correct
5 Correct 114 ms 10984 KB Output is correct
6 Correct 140 ms 10848 KB Output is correct
7 Correct 112 ms 10824 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 9084 KB Output is correct
2 Correct 111 ms 10388 KB Output is correct
3 Correct 202 ms 12360 KB Output is correct
4 Correct 135 ms 11336 KB Output is correct