| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 475479 |
2021-09-22T15:29:02 Z |
lukameladze |
Addk (eJOI21_addk) |
C++14 |
|
4 ms |
460 KB |
# include <bits/stdc++.h>
#define f first
#define int long long
#define s second
#define pb push_back
using namespace std;
const int N = 5e5 + 5;
int le1,ri1,pr[N],sf[N],pr1[N],a[N],q,n,ty,le,ri,m,ans,idx[N];
int tree[5][2*N];
int update(int idx, int val, int id) {
for (int i = idx; i < N; i += i&(-i)) {
tree[id][i] += val;
}
}
int getans(int idx, int id) {
int pas = 0;
for (int i = idx; i > 0; i-=i & (-i)) {
pas += tree[id][i];
}
return pas;
}
int getanss(int le , int ri) {
if (le > ri) return 0;
return getans(ri,0) - getans(le - 1,0);
}
int getans1(int le, int ri) {
if (le > ri) return 0;
return getans(ri,1) - getans(le - 1,1) - (le - 1) * getanss(le,ri);
}
int getans2(int le, int ri) {
if (le > ri) return 0;
return getans(ri,2) - getans(le - 1, 2) - (n - ri) * getanss(le, ri);
// return (sf[le] - sf[ri + 1] - (n - ri) * getans(le,ri));
}
main() {
int k;
cin>>n>>k;
for (int i = 1; i <= n; i++) {
cin>>a[i];
update(i,a[i],0);
update(i, i*a[i],1);
}
for (int i = n; i >= 1; i--){
update(i, (n - i + 1) * a[i],2);
}
cin>>q;
while (q -- ) {
cin>>ty;
if (ty == 2) {
cin>>le>>ri>>m;
if (m == 1) {
cout<<getanss(le,ri)<<endl;
continue;
}
if (2*m <= ri - le + 1) {
ans = m*getanss(le + m - 1,ri - m + 1);
ans += getans1(le, le + m - 2);
ans += getans2(ri - m + 2, ri);
}
else {
ans = 0;
ri1 = ri - m;
le1 = le + m;
ans += getans1(le,ri1);
ans += getans2(le1, ri);
ri1++; le1--;
ans += (ri1 - le + 1) * getanss(ri1,le1);
}
cout<<ans<<endl;
continue;
}
for (int i = 1; i <= k; i++) {
cin>>idx[i];
}
for (int i = 1; i < k; i++) {
int idxx = idx[i];
int idxx1= idx[i+1];
update(idxx, -a[idxx] + a[idxx1],0);
update(idxx, idxx * (-a[idxx] + a[idxx1]),1);
update(idxx, (n - idxx + 1) * (-a[idxx] + a[idxx1]), 2);
}
int idxx = idx[k]; int idxx1 = idx[1];
update(idxx, -a[idxx] + a[idxx1],0);
update(idxx, idxx * (-a[idxx] + a[idxx1]),1);
update(idxx, (n - idxx + 1) * (-a[idxx] + a[idxx1]), 2);
idx[k + 1] = idx[1];
for (int i = 1; i <= k; i++) {
a[idx[i]] = a[idx[i + 1]];
}
}
}
Compilation message
Main.cpp: In function 'long long int update(long long int, long long int, long long int)':
Main.cpp:14:1: warning: no return statement in function returning non-void [-Wreturn-type]
14 | }
| ^
Main.cpp: At global scope:
Main.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
36 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
