| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 880451 |
2023-11-29T12:46:02 Z |
Elvin_Fritl |
Addk (eJOI21_addk) |
C++17 |
|
380 ms |
14292 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
#define int long long
long long pre[N];
int n,k;
int a[N];
long long tree[N*3],trep[N*3],tres[N*3];
void built(int v,int l,int r)
{
if(l > r)
{
return;
}
if(l == r)
{
tree[v] = a[l];
trep[v] = a[l]*l;
tres[v] = a[l]*(n - l + 1);
///cerr << "l == " << l << " " << trep[v] << " " << tres[v] << endl;
return;
}
int mid=(l+r)>>1;
built(v*2,l,mid);
built(v*2 + 1,mid+1,r);
tree[v] = tree[v*2] + tree[v*2 + 1];
trep[v] = trep[v*2] + trep[v*2 + 1];
tres[v] = tres[v*2] + tres[v*2 + 1];
}
long long get(int v,int l,int r,int ml,int mr)
{
if(l > r || ml > r || mr < l)
{
return 0;
}
if(ml <= l && r <= mr)
{
return tree[v];
}
int mid=(l+r)>>1;
return get(v*2 , l , mid , ml , mr) + get(v*2 + 1,mid + 1,r,ml,mr);
}
long long getp(int v,int l,int r,int ml,int mr)
{
if(l > r || ml > r || mr < l)
{
return 0;
}
if(ml <= l && r <= mr)
{
return trep[v];
}
int mid=(l+r)>>1;
return getp(v*2 , l , mid , ml , mr) + getp(v*2 + 1,mid + 1,r,ml,mr);
}
long long gets(int v,int l,int r,int ml,int mr)
{
if(l > r || ml > r || mr < l)
{
return 0;
}
if(ml <= l && r <= mr)
{
return tres[v];
}
int mid=(l+r)>>1;
return gets(v*2 , l , mid , ml , mr) + gets(v*2 + 1,mid + 1,r,ml,mr);
}
void update(int v,int l,int r,int ind,int val)
{
if(l > r)
{
return;
}
if(l == r)
{
a[l] = val;
tree[v] = a[l];
trep[v] = a[l]*l;
tres[v] = a[l]*(n - l + 1);
///cerr << "l == " << ind << " " << trep[v] << " " << tres[v] << endl;
return;
}
int mid=(l+r)>>1;
if(ind <= mid){
update(v*2,l,mid,ind,val);
}
else{
update(v*2 + 1,mid+1,r,ind,val);
}
tree[v] = tree[v*2] + tree[v*2 + 1];
trep[v] = trep[v*2] + trep[v*2 + 1];
tres[v] = tres[v*2] + tres[v*2 + 1];
}
long long prf(int l, int r){
long long sum = getp(1,1,n,l,r);
sum -= (l - 1) * (get(1, 1, n, l, r));
return sum;
}
long long syf(int l, int r){
long long sum = gets(1,1,n,l,r);
///cerr << "suf "<< sum <<endl;
///assert(sum == sum2);
sum -= (n - r) * get(1, 1, n, l, r);
return sum;
}
int32_t main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i] = pre[i-1] + a[i];
}
built(1,1,n);
if(n <= 10000 && k == 1){
int q;
cin>>q;
while(q--){
int ty;
cin>>ty;
if(ty == 2){
int l,r,m;
cin>>l>>r>>m;
long long res=0;
for(int i=l + m - 1; i<=r; i++){
res+=pre[i]-pre[i-m];
}
cout << res << endl;
}
else{
int m;
cin>>m;
}
}
return 0;
}
int q;
cin>>q;
while(q--)
{
int ty;
cin>>ty;
if(ty == 2){
int l,r;
long long m;
cin>>l>>r>>m;
assert(r >= l);
if((r - l + 1) >= m*2){
assert(l + m - 1 <= r - m + 1);
long long res = get(1,1,n,l + (m - 1) , r - (m - 1))*m;
assert(l + m - 2 <= r - m + 2);
res += prf(l, l + m - 2);
res += syf(r - m + 2, r);
cout << res << endl;
}
else{
int cur_m = r - l + 2 - m;
assert(cur_m <= m && cur_m > 0);
///cur_m
long long res = 0;
///assert(l + cur_m == r - cur_m);
res += prf(l, l + cur_m - 1);
res += syf(r - cur_m + 1, r);
///cerr << r - cur_m << " " << l + cur_m << endl;
res += get(1, 1, n, l + cur_m, r - cur_m) * cur_m;
///cerr<<"3 ";
cout << res << endl;
}
}
else{
vector<int>ind;
for(int i=0;i<k;i++){
int x;
cin>>x;
ind.push_back(x);
}
int fi = a[ind[0]];
for(int i=1;i<k;i++){
update(1,1,n,ind[i-1],a[ind[i]]);
}
update(1,1,n,ind[k-1],fi);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
6 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
13 ms |
6640 KB |
Output is correct |
| 5 |
Correct |
12 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
20 ms |
6744 KB |
Output is correct |
| 7 |
Correct |
21 ms |
6748 KB |
Output is correct |
| 8 |
Correct |
26 ms |
6944 KB |
Output is correct |
| 9 |
Correct |
43 ms |
9052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
9532 KB |
Output is correct |
| 2 |
Correct |
98 ms |
9808 KB |
Output is correct |
| 3 |
Correct |
136 ms |
10308 KB |
Output is correct |
| 4 |
Correct |
231 ms |
11348 KB |
Output is correct |
| 5 |
Correct |
346 ms |
12996 KB |
Output is correct |
| 6 |
Correct |
312 ms |
12648 KB |
Output is correct |
| 7 |
Correct |
318 ms |
13028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
174 ms |
11168 KB |
Output is correct |
| 2 |
Correct |
283 ms |
12336 KB |
Output is correct |
| 3 |
Correct |
380 ms |
14292 KB |
Output is correct |
| 4 |
Correct |
369 ms |
13140 KB |
Output is correct |
