| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 484784 |
2021-11-05T13:15:32 Z |
fuad27 |
Addk (eJOI21_addk) |
C++17 |
|
429 ms |
7604 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;
}
int n, k;
int32_t main () {
cin >> n >> k;
int arr[n+1], prefix1[n+1] = {0}, prefix2[n+1] = {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];
}
if(k > 1) {
segment_tree<int> s1;
s1.fun = op;
segment_tree<int> s2;
s2.fun = op;
arr[0] = 0;
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 asdf1;
cin >> asdf1;
if(asdf1 == 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:87:8: warning: unused variable 'ans' [-Wunused-variable]
87 | int ans = 0;
| ^~~
Main.cpp:112:8: warning: unused variable 'ans' [-Wunused-variable]
112 | int ans = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3404 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3532 KB |
Output is correct |
| 4 |
Correct |
9 ms |
3532 KB |
Output is correct |
| 5 |
Correct |
11 ms |
3532 KB |
Output is correct |
| 6 |
Correct |
13 ms |
3712 KB |
Output is correct |
| 7 |
Correct |
14 ms |
3660 KB |
Output is correct |
| 8 |
Correct |
18 ms |
3788 KB |
Output is correct |
| 9 |
Correct |
23 ms |
3916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
4292 KB |
Output is correct |
| 2 |
Correct |
72 ms |
4676 KB |
Output is correct |
| 3 |
Correct |
93 ms |
5160 KB |
Output is correct |
| 4 |
Correct |
176 ms |
6288 KB |
Output is correct |
| 5 |
Correct |
261 ms |
7604 KB |
Output is correct |
| 6 |
Correct |
207 ms |
7280 KB |
Output is correct |
| 7 |
Correct |
209 ms |
7236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
5380 KB |
Output is correct |
| 2 |
Correct |
282 ms |
6636 KB |
Output is correct |
| 3 |
Correct |
429 ms |
6724 KB |
Output is correct |
| 4 |
Correct |
351 ms |
7492 KB |
Output is correct |
