Submission #613766

#	Time	Username	Problem	Language	Result	Execution time	Memory
613766		karelisp	Addk (eJOI21_addk)	C++14	0 / 100	138 ms	3912 KiB

Main

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

int N, K, Q;
long long a[100005], pf1[100005], pf2[100005];

struct SegTree{
	long long st[400005];

	void update(int pos, long long val, int v=1, int start=1, int end=N){
		if(start==end){
			st[v] = val;
			return;
		}

		int mid = (start+end)/2;
		if(pos<=mid) update(pos, val, 2*v, start, mid);
		else update(pos, val, 2*v+1, mid+1, end);
		st[v] = st[2*v] + st[2*v+1];
	}

	long long query(int l, int r, int v=1, int start=1, int end=N){
		if(l>r)
			return 0;
		if(l==start && r==end)
			return st[v];

		int mid = (start+end)/2;
		if(r<=mid) return query(l, r, 2*v, start, mid);
		else if(l>mid) return query(l, r, 2*v+1, mid+1, end);
		else return query(l, mid, 2*v, start, mid) + query(mid+1, r, 2*v+1, mid+1, end);
	}
}st_sum, st_mulsum;


long long sum(int l, int r){
	return st_sum.query(l,r);
}

long long mulsum(int l, int r){
	return st_mulsum.query(l,r);
}

long long answer(long long int l, long long int r, long long m){
	if(2*m <= r-l+1){
		long long S1 = mulsum(l, l+m-1) + (1-l)*sum(l, l+m-1);
		long long S2 = m * sum(l+m, r-m);
		long long S3 = (r+1) * sum(r-m+1, r) - mulsum(r-m+1, r);
		return S1 + S2 + S3;
	}
	else{
		int d = r-l+1-m;
		long long S1 = mulsum(l, l+d-1) + (1-l)*sum(l, l+d-1);
		long long S2 = (d+1)*sum(l+d, r-d);
		long long S3 = (r+1)*sum(r-d+1, r) - mulsum(r-d+1, r);
		return S1 + S2 + S3;
	}
}

int main(){
	scanf("%d%d", &N, &K);
	for(long long i=1; i<=N; i++){
		scanf("%lld", &a[i]);
		st_sum.update(i, a[i]);
		st_mulsum.update(i, i*a[i]);
	}

	scanf("%d", &Q);
	for(int l,r,m,op,q=0; q<Q; q++){
		scanf("%d", &op);
		if(op==1){
			int cur, prev;
			scanf("%d",&prev);
			int first_val = st_sum.query(prev, prev);
			for(int i= 2 ; i <=  K ; i++)
			{
				scanf("%d",&cur);
				long long A_cur = st_sum.query(cur, cur);
				st_sum.update(prev, A_cur);
				st_mulsum.update(prev, prev*A_cur);
				prev = cur;
			}
			st_sum.update(prev, first_val);
			st_mulsum.update(prev, prev*first_val);

		}
		else{
			scanf("%d%d%d", &l, &r, &m);
			printf("%lld\n", answer(l,r,m));
		}
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%lld", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
Main.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
Main.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d", &op);
      |   ~~~~~^~~~~~~~~~~
Main.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |    scanf("%d",&prev);
      |    ~~~~~^~~~~~~~~~~~
Main.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d",&cur);
      |     ~~~~~^~~~~~~~~~~
Main.cpp:88:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |    scanf("%d%d%d", &l, &r, &m);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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