| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 880163 |
2023-11-28T22:34:08 Z |
YassirSalama |
Addk (eJOI21_addk) |
C++17 |
|
715 ms |
22300 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include<assert.h>
#include <functional>
#include <iterator>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=2e5+100;
struct Node{
int sum1p;//a+b+c+d+....
int sum2p;//a*1+b*2+c*3+d*4.....
int sum1s;//z+y+w+x+.....
int sum2s;//z*1+y*2+w*3
int lz;
bool lazy=false;
Node* left,*right;
Node(){
left=nullptr,right=nullptr;
sum1p=sum2p=sum1s=sum2s=0;
lz=-1;
lazy=false;
}
};
Node* root;
int arr[MAXN];
int n;
void build(Node* node,int l,int r){
if(l==r){
int x=arr[l];
node->sum1p+=x;
node->sum2p+=x*l;
node->sum1s+=x;
node->sum2s+=x*(n-l+1);
return;
}
int mid=(l+r)/2;
node->left=new Node();
node->right=new Node();
build(node->left,l,mid);
build(node->right,mid+1,r);
node->sum1p=node->left->sum1p+node->right->sum1p;
node->sum2p=node->left->sum2p+node->right->sum2p;
node->sum1s=node->left->sum1s+node->right->sum1s;
node->sum2s=node->left->sum2s+node->right->sum2s;
}
void update(Node* node,int l,int r,int ql,int x,int i){
if(l==r){
switch(i){
case 1:
node->sum1p=x;
break;
case 2:
node->sum2p=x;
break;
case 3:
node->sum1s=x;
break;
case 4:
node->sum2s=x;
break;
}
return;
}
int mid=(l+r)/2;
if(ql<=mid) update(node->left,l,mid,ql,x,i);
else{
update(node->right,mid+1,r,ql,x,i);
}
node->sum1p=node->left->sum1p+node->right->sum1p;
node->sum2p=node->left->sum2p+node->right->sum2p;
node->sum1s=node->left->sum1s+node->right->sum1s;
node->sum2s=node->left->sum2s+node->right->sum2s;
}
int query(Node* node,int l,int r,int ql,int qr,int i){
if(ql<=l&&r<=qr){
switch(i){
case 1:
return node->sum1p;
break;
case 2:
return node->sum2p;
break;
case 3:
return node->sum1s;
break;
case 4:
return node->sum2s;
break;
}
return 0;
}
int mid=(l+r)/2,ans=0;
if(ql<=mid) ans+=query(node->left,l,mid,ql,qr,i);
if(qr>mid) ans+=query(node->right,mid+1,r,ql,qr,i);
return ans;
}
signed main(){
root=new Node();
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
int q;
cin>>q;
build(root,1,n);
while(q--){
int t;
cin>>t;
if(t==1){
vector<int> d(k);
vector<int> c(k);
for(int i=0;i<k;i++){
cin>>d[i];
c[i]=arr[d[i]];
update(root,1,n,d[i],0,1);
update(root,1,n,d[i],0,2);
update(root,1,n,d[i],0,3);
update(root,1,n,d[i],0,4);
}
// dbg("done")
// continue;
int x=*d.rbegin();
d.pop_back();
d.insert(d.begin(),x);
// OVL(d," ")
// OVL(c," ")
for(int i=0;i<k;i++){
arr[d[i]]=c[i];
update(root,1,n,d[i],arr[d[i]],1);
update(root,1,n,d[i],arr[d[i]]*(d[i]),2);
update(root,1,n,d[i],arr[d[i]],3);
update(root,1,n,d[i],arr[d[i]]*(n-d[i]+1),4);
// dbg(d[i],c[i],query(root,1,n,d[i],d[i],1))
}
// OVL(arr," ")
}
else{
int l,r,m;
cin>>l>>r>>m;
int ans=0;
if(r-l+1>=2*m){
int ql=min(l+m-1,r-m+1);
int qr=max(r-m+1,l+m-1);
// dbg(ql,qr)
ans+=query(root,1,n,ql,qr,1)*min(m,(ql-l+1));
ql--;
qr++;
// dbg(ql,qr,ans,2)
ans+=query(root,1,n,l,ql,2)-
query(root,1,n,l,ql,1)*(l-1);
// dbg(ans,1,l,ql,query(root,1,n,l,ql,1))
ans+=query(root,1,n,qr,r,4)-
query(root,1,n,qr,r,3)*(n-r);
cout<<ans<<endl;
}else{
int ql=min(l+m-1,r-m+1);
int qr=max(r-m+1,l+m-1);
// dbg(ql,qr,ql-l+1)
ans+=query(root,1,n,ql,qr,1)*min(m,(ql-l+1));
ql--;
qr++;
// dbg(ql,qr,ans)
ans+=query(root,1,n,l,ql,2)-
query(root,1,n,l,ql,1)*(l-1);
// dbg(ans,1,query(root,1,n,l,ql,1),query(root,1,n,l,ql,2))
ans+=query(root,1,n,qr,r,4)-
query(root,1,n,qr,r,3)*(n-r);
// dbg(ans,qr,r,query(root,1,n,qr,r,4))
cout<<ans<<endl;
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
648 KB |
Output is correct |
| 3 |
Correct |
3 ms |
720 KB |
Output is correct |
| 4 |
Correct |
4 ms |
972 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1616 KB |
Output is correct |
| 8 |
Correct |
10 ms |
1756 KB |
Output is correct |
| 9 |
Correct |
14 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
3920 KB |
Output is correct |
| 2 |
Correct |
46 ms |
6480 KB |
Output is correct |
| 3 |
Correct |
65 ms |
8532 KB |
Output is correct |
| 4 |
Correct |
125 ms |
14676 KB |
Output is correct |
| 5 |
Correct |
202 ms |
20856 KB |
Output is correct |
| 6 |
Correct |
193 ms |
20556 KB |
Output is correct |
| 7 |
Correct |
185 ms |
20560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
233 ms |
9040 KB |
Output is correct |
| 2 |
Correct |
271 ms |
16980 KB |
Output is correct |
| 3 |
Correct |
715 ms |
22300 KB |
Output is correct |
| 4 |
Correct |
256 ms |
20968 KB |
Output is correct |
