Submission #880163

#	Time	Username	Problem	Language	Result	Execution time	Memory
880163		YassirSalama	Addk (eJOI21_addk)	C++17	100 / 100	715 ms	22300 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include<assert.h>
#include <functional>
#include <iterator>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=2e5+100;
struct Node{
	int sum1p;//a+b+c+d+....
	int sum2p;//a*1+b*2+c*3+d*4.....

	int sum1s;//z+y+w+x+.....
	int sum2s;//z*1+y*2+w*3

	int lz;
	bool lazy=false;

	Node* left,*right;
	Node(){
		left=nullptr,right=nullptr;
		sum1p=sum2p=sum1s=sum2s=0;
		lz=-1;
		lazy=false;
	}
};
Node* root;
int arr[MAXN];
int n;
void build(Node* node,int l,int r){
	if(l==r){
		int x=arr[l];
		node->sum1p+=x;
		node->sum2p+=x*l;
		node->sum1s+=x;
		node->sum2s+=x*(n-l+1);
		return;
	}
	int mid=(l+r)/2;
	node->left=new Node();
	node->right=new Node();
	build(node->left,l,mid);
	build(node->right,mid+1,r);
	node->sum1p=node->left->sum1p+node->right->sum1p;
	node->sum2p=node->left->sum2p+node->right->sum2p;
	node->sum1s=node->left->sum1s+node->right->sum1s;
	node->sum2s=node->left->sum2s+node->right->sum2s;

}
void update(Node* node,int l,int r,int ql,int x,int i){
	if(l==r){
		switch(i){
			case 1:
				node->sum1p=x;
				break;
			case 2:
				node->sum2p=x;
				break;
			case 3:
				node->sum1s=x;
				break;
			case 4:
				node->sum2s=x;
				break;	
		}
		return;
	}
	int mid=(l+r)/2;
	if(ql<=mid) update(node->left,l,mid,ql,x,i);
	else{
		update(node->right,mid+1,r,ql,x,i);
	}
	node->sum1p=node->left->sum1p+node->right->sum1p;
	node->sum2p=node->left->sum2p+node->right->sum2p;
	node->sum1s=node->left->sum1s+node->right->sum1s;
	node->sum2s=node->left->sum2s+node->right->sum2s;
}
int query(Node* node,int l,int r,int ql,int qr,int i){
	if(ql<=l&&r<=qr){
		switch(i){
			case 1:
				return node->sum1p;
				break;
			case 2:
				return node->sum2p;
				break;
			case 3:
				return node->sum1s;
				break;
			case 4:
				return node->sum2s;
				break;	
		}
		return 0;
	}
	int mid=(l+r)/2,ans=0;
	if(ql<=mid) ans+=query(node->left,l,mid,ql,qr,i);
	if(qr>mid) ans+=query(node->right,mid+1,r,ql,qr,i);
	return ans;
}
signed main(){
root=new Node();
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int k;
cin>>n>>k;
for(int i=1;i<=n;i++){
	cin>>arr[i];
}
int q;
cin>>q;
build(root,1,n);
while(q--){
	int t;
	cin>>t;
	if(t==1){
		vector<int> d(k);
		vector<int> c(k);
		for(int i=0;i<k;i++){
			cin>>d[i];
			c[i]=arr[d[i]];
			update(root,1,n,d[i],0,1);
			update(root,1,n,d[i],0,2);
			update(root,1,n,d[i],0,3);
			update(root,1,n,d[i],0,4);
		}
		// dbg("done")
		// continue;
		int x=*d.rbegin();
		d.pop_back();
		d.insert(d.begin(),x);
		// OVL(d," ")
		// OVL(c," ")
		for(int i=0;i<k;i++){
			arr[d[i]]=c[i];
			update(root,1,n,d[i],arr[d[i]],1);	
			update(root,1,n,d[i],arr[d[i]]*(d[i]),2);
			update(root,1,n,d[i],arr[d[i]],3);
			update(root,1,n,d[i],arr[d[i]]*(n-d[i]+1),4);
			// dbg(d[i],c[i],query(root,1,n,d[i],d[i],1))
		}
		// OVL(arr," ")
	}
	else{
		int l,r,m;
		cin>>l>>r>>m;
		int ans=0;
		if(r-l+1>=2*m){
			int ql=min(l+m-1,r-m+1);
			int qr=max(r-m+1,l+m-1);
			// dbg(ql,qr)
			ans+=query(root,1,n,ql,qr,1)*min(m,(ql-l+1));
			ql--;
			qr++;
			// dbg(ql,qr,ans,2)
			ans+=query(root,1,n,l,ql,2)-
			     query(root,1,n,l,ql,1)*(l-1);
			// dbg(ans,1,l,ql,query(root,1,n,l,ql,1))
			ans+=query(root,1,n,qr,r,4)-
			     query(root,1,n,qr,r,3)*(n-r);
			cout<<ans<<endl;
		}else{
			int ql=min(l+m-1,r-m+1);
			int qr=max(r-m+1,l+m-1);
			// dbg(ql,qr,ql-l+1)
			ans+=query(root,1,n,ql,qr,1)*min(m,(ql-l+1));
			ql--;
			qr++;
			// dbg(ql,qr,ans)
			ans+=query(root,1,n,l,ql,2)-
			     query(root,1,n,l,ql,1)*(l-1);
			// dbg(ans,1,query(root,1,n,l,ql,1),query(root,1,n,l,ql,2))
			ans+=query(root,1,n,qr,r,4)-
			     query(root,1,n,qr,r,3)*(n-r);
			// dbg(ans,qr,r,query(root,1,n,qr,r,4))
			cout<<ans<<endl;
		}
	}
}
}

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