| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 593517 |
2022-07-11T10:13:46 Z |
serkanrashid |
Addk (eJOI21_addk) |
C++14 |
|
354 ms |
12584 KB |
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e5+5;
int n,k,q;
long long a[maxn],b[maxn],pref[4*maxn],suff[4*maxn],tree[4*maxn];
long long ql,qr,val;
void make_tree(int v, int l, int r)
{
if(l==r)
{
pref[v]=a[r]*r;
suff[v]=a[r]*(n-r+1);
tree[v]=a[r];
return;
}
int mid=(l+r)/2;
make_tree(v*2+0,l,mid+0);
make_tree(v*2+1,mid+1,r);
pref[v]=pref[v*2]+pref[v*2+1];
suff[v]=suff[v*2]+suff[v*2+1];
tree[v]=tree[v*2]+tree[v*2+1];
}
void update(int v, int l, int r)
{
if(l>qr||r<ql||l>r) return;
if(l>=ql&&r<=qr)
{
pref[v]=val*r;
suff[v]=val*(n-r+1);
tree[v]=val;
return;
}
int mid=(l+r)/2;
update(v*2+0,l,mid+0);
update(v*2+1,mid+1,r);
pref[v]=pref[v*2]+pref[v*2+1];
suff[v]=suff[v*2]+suff[v*2+1];
tree[v]=tree[v*2]+tree[v*2+1];
}
long long query_pref(int v, int l, int r)
{
if(l>qr||r<ql||l>r) return 0;
if(l>=ql&&r<=qr) return pref[v];
int mid=(l+r)/2;
return query_pref(v*2+0,l,mid+0) + query_pref(v*2+1,mid+1,r);
}
long long query_suff(int v, int l, int r)
{
if(l>qr||r<ql||l>r) return 0;
if(l>=ql&&r<=qr) return suff[v];
int mid=(l+r)/2;
return query_suff(v*2+0,l,mid+0) + query_suff(v*2+1,mid+1,r);
}
long long query_tree(int v, int l, int r)
{
if(l>qr||r<ql||l>r) return 0;
if(l>=ql&&r<=qr) return tree[v];
int mid=(l+r)/2;
return query_tree(v*2+0,l,mid+0) + query_tree(v*2+1,mid+1,r);
}
void read()
{
cin >> n >> k;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
make_tree(1,1,n);
cin >> q;
int ch,l,r,m,idx,mid,obr;
long long ans=0;
for(int i=1;i<=q;i++)
{
cin >> ch;
ans=0;
if(ch==1)
{
for(int j=1;j<=k;j++)
{
cin >> b[j];
}
long long pom_val=0;
ql=b[1];
qr=b[1];
pom_val=query_tree(1,1,n);
for(int j=1;j<k;j++)
{
ql=b[j+1];
qr=b[j+1];
val=query_tree(1,1,n);
ql=b[j];
qr=b[j];
update(1,1,n);
}
val=pom_val;
ql=b[k];
qr=b[k];
update(1,1,n);
}
else
{
cin >> l >> r >> m;
m=min(m,r-l+2-m);
idx=l+m-1;
mid=(l+r)/2;
idx=min(idx,mid);
m=idx-l+1;
ql=l;
qr=idx-1;
ans+=query_pref(1,1,n);
ans-=query_tree(1,1,n)*(l-1);
obr=l+r-idx;
ql=obr+1;
qr=r;
ans+=query_suff(1,1,n);
ans-=query_tree(1,1,n)*(n-r);
ql=idx;
qr=obr;
ans+=query_tree(1,1,n)*(idx-l+1);
cout << ans << endl;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
read();
return 0;
}
/*
8 1
7 2 5 1 9 3 4 6
6
2 3 8 4
2 5 6 2
2 6 8 1
2 1 8 4
2 1 8 6
2 3 7 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
468 KB |
Output is correct |
| 4 |
Correct |
5 ms |
596 KB |
Output is correct |
| 5 |
Correct |
7 ms |
596 KB |
Output is correct |
| 6 |
Correct |
9 ms |
836 KB |
Output is correct |
| 7 |
Correct |
10 ms |
852 KB |
Output is correct |
| 8 |
Correct |
11 ms |
852 KB |
Output is correct |
| 9 |
Correct |
15 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
2296 KB |
Output is correct |
| 2 |
Correct |
52 ms |
2540 KB |
Output is correct |
| 3 |
Correct |
69 ms |
4196 KB |
Output is correct |
| 4 |
Correct |
129 ms |
8096 KB |
Output is correct |
| 5 |
Correct |
214 ms |
8692 KB |
Output is correct |
| 6 |
Correct |
184 ms |
8596 KB |
Output is correct |
| 7 |
Correct |
176 ms |
8604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
4224 KB |
Output is correct |
| 2 |
Correct |
203 ms |
10808 KB |
Output is correct |
| 3 |
Correct |
354 ms |
12584 KB |
Output is correct |
| 4 |
Correct |
249 ms |
11480 KB |
Output is correct |
