| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1031225 |
2024-07-22T16:15:39 Z |
Dennis_Jason |
Addk (eJOI21_addk) |
C++14 |
|
405 ms |
15700 KB |
#include <bitset>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#define int long long
#define pb push_back
#define MOD 1000000007
#define NMAX 100005
#define nl '\n'
#define INF 1000000007
#define pii1 pair<int, pair<int,int>> (1,(1,2));
#define pii pair<int,int>
#define tpl tuple<int,int,int>
using namespace std;
ifstream fin("data.in");
ofstream fout("data.out");
struct item{
int sum,pref,suf;
};
class segtree{
private:
int n;
vector<item>tree;
public:
void init(int sz)
{
n=sz;
tree.resize(4*sz+1);
}
item single(int val,int pos)
{
return{
val,
pos*val,
(n-pos+1)*val
};
}
item calc(item a,item b)
{
return{
a.sum+b.sum,
a.pref+b.pref,
a.suf+b.suf
};
}
void update(int node,int st,int dr,int pos,int val)
{
if(st==dr)
{
tree[node]=single(val,st);
return;
}
int mid=(st+dr)/2;
if(pos<=mid)
update(2*node,st,mid,pos,val);
else
update(2*node+1,mid+1,dr,pos,val);
tree[node]=calc(tree[2*node],tree[2*node+1]);
}
item query(int node,int st,int dr,int L,int R)
{
if(R<st || dr<L)
return {0,0,0};
if(L<=st && dr<=R)
{
return tree[node];
}
int mid=(st+dr)/2;
item left=query(2*node,st,mid,L,R);
item right=query(2*node+1,mid+1,dr,L,R);
return calc(left,right);
}
void update(int pos,int val)
{
update(1,1,n,pos,val);
}
item query(int L,int R)
{
return query(1,1,n,L,R);
}
};
/*
*
*
------EXAMPLE-----
1 2 3 4 5 6 7 8
7 2 5 1 9 3 4 6
2 2 7 4
m=4, length=6
2 5 1 9 3 4
2+5+1+9=17
5+1+9+3=18
1+9+3+4=17
2*1,5*2,1*3,9*3,3*2,4*1
m=min(4,6-4+1)
m=min(4,3)
m=3;
x=(l+m-1)=2+3-1=4
y=5
3*2+4*1=10
3+4=7
3*3+4*2=17
---------DEMONSTRATION------------
m=min(m,(r-l+1)-m+1)
m=min(12,(20-5+1)-12+1)
m=min(12,(15+1)-12+1)
m=min(12,(16-12+1))
m=min(12,5),5
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
elm 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5
1 2 3 4 5 6 7 8 9 10 11 12=78
2 3 4 5 6 7 8 9 10 11 12 13=90
3 4 5 6 7 8 9 10 11 12 13 14=102
4 5 6 7 8 9 10 11 12 13 14 15=114
5 6 7 8 9 10 11 12 13 14 15 16=126
total =510
1*1,2*2,3*3,4*4,5*5,6*5,7*5,8*5,9*5,10*5,11*5,12*5,13*4,14*3,15*2,16*1 ->> max freq is new m
x=(l+m-1)=5+5-1=9
y=(r-m+1)=20-5+1=16 from x to y is maxim freq
1. First is sum(x,y).sum*m=68*m=340;
I need to find sum from (l,x-1) and(y+1,r)
Sum(l,x-1)
ind:5 6 7 8
1*1,2*2,3*3,4*4/ this is here, is the elem * ind, but the real ind is 5,6,7,8
1*5,2*6,3*7,4*8
1*20,2*18,3*17,4*16
let's calculate:
i need 1+4+9+16=30
1+2+3+4=10*(5-1)=40
5+12+21+32=17+53=70-40=30 this is true
Second sum is sum(l,x-1).pref-sum(l,x-1).sum*(l-1)
SUM(y+1,r)
ind:17 18 19 20
i need:13*4+14*3+15*2+16*1=140
13+14+15+16=30+28=58
Third sum(y+1,r).suf-sum(y+1,r)*(n-r)
*/
segtree st;
void solve()
{
int n,k;
cin>>n>>k;
vector<int>v(n+1);
st.init(n);
for(int i=1;i<=n;++i)
{
cin>>v[i];
st.update(i,v[i]);
}
int q;
cin>>q;
while(q--)
{
int type;
cin>>type;
if(type==1)
{
vector<int>ind(k+1);
for(int i=1;i<=k;++i)
cin>>ind[i];
// v[ind[1]]=v[ind[2]]
//...................
///v[ind[k]]=v[ind[1]]
vector<int>val(k+1);
for(int i=1;i<=k;++i)
{
val[i]=st.query(ind[i],ind[i]).sum;
}
for(int i=1;i<k;++i)
{
st.update(ind[i],val[i+1]);
}
st.update(ind[k],val[1]);
}
else
{
int l,r,m;
cin>>l>>r>>m;
m=min(m,(r-l+1)-m+1);
int x=(l+m-1);
int y=(r-m+1);
int ans=0;
item sum1=st.query(l,x-1);
item sum2=st.query(x,y);
item sum3=st.query(y+1,r);
ans+=(sum1.pref-sum1.sum*(l-1));
ans+=(sum2.sum*m);
ans+=(sum3.suf-sum3.sum*(n-r));
cout<<ans<<nl;
}
}
}
signed main() {
int t=1;
// cin>>t;
while(t--)
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
348 KB |
Output is correct |
| 3 |
Correct |
5 ms |
668 KB |
Output is correct |
| 4 |
Correct |
14 ms |
604 KB |
Output is correct |
| 5 |
Correct |
9 ms |
856 KB |
Output is correct |
| 6 |
Correct |
12 ms |
860 KB |
Output is correct |
| 7 |
Correct |
15 ms |
1140 KB |
Output is correct |
| 8 |
Correct |
18 ms |
1116 KB |
Output is correct |
| 9 |
Correct |
25 ms |
1540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
95 ms |
3668 KB |
Output is correct |
| 3 |
Correct |
119 ms |
5072 KB |
Output is correct |
| 4 |
Correct |
199 ms |
8448 KB |
Output is correct |
| 5 |
Correct |
309 ms |
11904 KB |
Output is correct |
| 6 |
Correct |
279 ms |
11900 KB |
Output is correct |
| 7 |
Correct |
263 ms |
11772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
177 ms |
5972 KB |
Output is correct |
| 2 |
Correct |
266 ms |
11936 KB |
Output is correct |
| 3 |
Correct |
405 ms |
15700 KB |
Output is correct |
| 4 |
Correct |
300 ms |
14672 KB |
Output is correct |
