oj.uz

Submission #613771

# Submission time Handle Problem Language Result Execution time Memory
613771 2022-07-30T10:34:46 Z karelisp Addk (eJOI21_addk) C++14
100 / 100
 337 ms 10436 KB 
#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){
			long long cur, prev;
			scanf("%lld",&prev);
			long long first_val = st_sum.query(prev, prev);
			for(int i= 2 ; i <=  K ; i++)
			{
				scanf("%lld",&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

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("%lld",&prev);
      |    ~~~~~^~~~~~~~~~~~~~
Main.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%lld",&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
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 6 ms 588 KB Output is correct
6 Correct 7 ms 708 KB Output is correct
7 Correct 9 ms 820 KB Output is correct
8 Correct 10 ms 800 KB Output is correct
9 Correct 15 ms 1096 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1740 KB Output is correct
2 Correct 52 ms 2032 KB Output is correct
3 Correct 66 ms 3404 KB Output is correct
4 Correct 116 ms 6172 KB Output is correct
5 Correct 209 ms 6860 KB Output is correct
6 Correct 172 ms 6792 KB Output is correct
7 Correct 169 ms 6740 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 3156 KB Output is correct
2 Correct 185 ms 8460 KB Output is correct
3 Correct 337 ms 10436 KB Output is correct
4 Correct 230 ms 9376 KB Output is correct