oj.uz

Submission #484781

# Submission time Handle Problem Language Result Execution time Memory
484781 2021-11-05T13:06:58 Z fuad27 Addk (eJOI21_addk) C++17
8 / 100
 422 ms 7420 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];
if(k > 1) {
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;
    	}
}
}
else {
			int q;
	cin >> q;
	while(q--) {
		int k;
		cin >> k;
		if(k == 1) {
			int d;
			cin >> d;
		}
		else {
			int ans = 0;
			int l, r, m;
			cin >> l >> r >> m;
			m = min(r-l-m + 2, m);
			int a = (prefix2[l+m-1] - prefix2[l-1])-(prefix1[l+m-1] - prefix1[l-1])*(l-1);
			int b = (prefix1[r-m] - prefix1[l+m-1])*m;
			int c = (prefix1[r] - prefix1[r-m])*(r+1) - (prefix2[r] - prefix2[r-m]);
		       cout<<a+b+c<<endl;
		}
	}
}
}

Compilation message

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

Subtask #1
0 / 36.0

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

Subtask #2
0 / 56.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 5492 KB Output is correct
2 Correct 261 ms 6608 KB Output is correct
3 Correct 422 ms 6888 KB Output is correct
4 Correct 320 ms 7420 KB Output is correct