oj.uz

Submission #484778

# Submission time Handle Problem Language Result Execution time Memory
484778 2021-11-05T12:56:35 Z fuad27 Addk (eJOI21_addk) C++17
64 / 100
 503 ms 9440 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAX_SEGMENT_TREE_SIZE = 100000 + 10;
template<class T> class segment_tree {
    int n = MAX_SEGMENT_TREE_SIZE;
    T t[2*MAX_SEGMENT_TREE_SIZE + 2] = {0};
    public:
        T intializer = 0;
        std::function<T(T,T)> fun;
        void build(T arr[], int sz) {
            for(int i = 0;i<n;i++) {
                t[i+n] = arr[i];
            }
            for(int i = n-1;i>0;i--) {
                t[i] = fun(t[i*2], t[i*2 + 1]);
            }
        }
        void modify(int p, T value) {
            for(t[p+=n]=value;p>1;p>>=1) {
                t[p>>1] = fun(t[p], t[p^1]);
            }
        }
        T query(int l, int r) {
	    swap(l, r);
	    r++,l++;
            T ans = intializer;
            for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
                if(l&1)ans=fun(ans, t[l++]);
                if(r&1)ans=fun(ans, t[--r]);
            }
            return ans;
        }
};
 
long long op(long long a, long long b) {
    return a+b;
}
int32_t main () {
	int n, k;
	cin >> n >> k;
	segment_tree<int> s1;
	s1.fun = op;
	segment_tree<int> s2;
	s2.fun = op;
	int arr[n+1]/*, prefix1[n+1] = {0}, prefix2[n+1] = {0}*/;
	arr[0] = 0;
	for(int i = 1;i<=n;i++) {
		cin >> arr[i];
		//prefix2[i] = prefix2[i-1] + arr[i]*i;
		//prefix1[i] = prefix1[i-1] + arr[i];
	}
	s1.build(arr, n+1);
	for(int i = 1;i<=n;i++) {
		arr[i]*=i;
	}

	s2.build(arr, n+1);
	for(int i = 1;i<=n;i++) {
		arr[i]/=i;
	}


	int q=1;
	cin >> q;
	int asdf[k];
	while(q--) {
		int q;
		cin >> q;
		if(q == 1) {
			for(int i = 0;i<k;i++) {
				cin >> asdf[i];
			}
			reverse(asdf, asdf+k);
			long long prev = arr[asdf[k-1]];
			for(int i = 0;i<k;i++) {
				swap(prev, arr[asdf[i]]);
			}
			for(int i = 0;i<k;i++) {
				s1.modify(asdf[i], arr[asdf[i]]);
				s2.modify(asdf[i], arr[asdf[i]]*asdf[i]);
			}
		}
		else {
			int ans = 0;
			int l, r, m;
			cin >> l >> r >> m;
			m = min(r-l-m + 2, m);
			int a = s2.query(l+m-1, l-1) - s1.query(l+m-1, l-1)*(l-1);
			//int a1 = (prefix2[l+m-1] - prefix2[l-1])-(prefix1[l+m-1] - prefix1[l-1])*(l-1);
			//int b1 = (prefix1[r-m] - prefix1[l+m-1])*m;
			int b = s1.query(r-m, l+m-1)*m;
			//int c1 = (prefix1[r] - prefix1[r-m])*(r+1) - (prefix2[r] - prefix2[r-m]);
			int c = s1.query(r, r-m)*(r+1) - s2.query(r, r-m);
		        cout<<a+b+c<<endl;
		}
	}
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:85:8: warning: unused variable 'ans' [-Wunused-variable]
   85 |    int ans = 0;
      |        ^~~

Subtask #1
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4356 KB Output is correct
2 Correct 105 ms 4740 KB Output is correct
3 Correct 139 ms 5200 KB Output is correct
4 Correct 237 ms 6876 KB Output is correct
5 Correct 337 ms 8112 KB Output is correct
6 Correct 317 ms 8004 KB Output is correct
7 Correct 330 ms 7876 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 6168 KB Output is correct
2 Correct 307 ms 7548 KB Output is correct
3 Correct 503 ms 9440 KB Output is correct
4 Correct 354 ms 8436 KB Output is correct