oj.uz

답안 #880163

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
880163 2023-11-28T22:34:08 Z YassirSalama Addk (eJOI21_addk) C++17
100 / 100
 715 ms 22300 KB 
#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.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 648 KB Output is correct
3 Correct 3 ms 720 KB Output is correct
4 Correct 4 ms 972 KB Output is correct
5 Correct 6 ms 1116 KB Output is correct
6 Correct 7 ms 1372 KB Output is correct
7 Correct 8 ms 1616 KB Output is correct
8 Correct 10 ms 1756 KB Output is correct
9 Correct 14 ms 2396 KB Output is correct

Subtask #2
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 3920 KB Output is correct
2 Correct 46 ms 6480 KB Output is correct
3 Correct 65 ms 8532 KB Output is correct
4 Correct 125 ms 14676 KB Output is correct
5 Correct 202 ms 20856 KB Output is correct
6 Correct 193 ms 20556 KB Output is correct
7 Correct 185 ms 20560 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 9040 KB Output is correct
2 Correct 271 ms 16980 KB Output is correct
3 Correct 715 ms 22300 KB Output is correct
4 Correct 256 ms 20968 KB Output is correct