| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 700174 |
2023-02-18T18:33:15 Z |
pera |
Addk (eJOI21_addk) |
C++14 |
|
401 ms |
12472 KB |
#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define pb push_back
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const ll mod = 1e9 + 7 , N = 1e5 + 100;
ll n , A[N] , t[4 * N][3] , k;
void bld(ll v, ll tl, ll tr) {
if (tl == tr) {
t[v][0] = A[tl];
t[v][1] = (tl + 1) * A[tl];
t[v][2] = (n - tl) * A[tl];
} else {
ll tm = (tl + tr) / 2;
bld(v * 2 , tl, tm);
bld(v * 2 + 1, tm + 1, tr);
for(int w = 0;w < 3;w ++){
t[v][w] = t[v * 2][w] + t[v * 2 + 1][w];
}
}
}
void upd(ll v, ll tl, ll tr, ll pos, ll val) {
if (tl == tr) {
t[v][0] = val;
t[v][1] = (tl + 1) * val;
t[v][2] = (n - tl) * val;
}else {
ll tm = (tl + tr) / 2;
if (pos <= tm){
upd(v * 2 , tl , tm , pos ,val);
}else{
upd(v * 2 + 1 , tm + 1, tr, pos ,val);
}
for(int w = 0;w < 3;w ++){
t[v][w] = t[v * 2][w] + t[v * 2 + 1][w];
}
}
}
ll sm(ll v, ll tl, ll tr, ll l, ll r , int p) {
if (l > r)
return 0;
if (l == tl && r == tr) {
return t[v][p];
}
ll tm = (tl + tr) / 2;
return sm(v * 2, tl, tm, l , min(r , tm) , p)
+ sm(v * 2 + 1 , tm + 1, tr , max(l, tm + 1) , r , p);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> k;
for(int i = 0;i < n;i ++){
cin >> A[i];
}
bld(1 , 0 , n - 1);
ll Q;cin >> Q;
while(Q --){
int tt;cin >> tt;
if(tt == 1){
vector<ll> inds(k) , nw;
for(int i = 0;i < k;i ++){
cin >> inds[i];
-- inds[i];
if(i) nw.pb(inds[i]);
}
if(k == 1){
continue;
}
nw.pb(inds[0]);
vector<ll> vls;
for(int i = 0;i < k;i ++){
vls.pb(A[nw[i]]);
}
for(int i = 0; i < k;i ++){
A[inds[i]] = vls[i];
upd(1 , 0 , n - 1 , inds[i] , vls[i]);
}
// for(int i = 0;i < n;i ++){
// cout << A[i] << " ";
// }
// cout << endl;
}else{
ll l , r , m;cin >> l >> r >> m;
-- l , -- r;
ll sz = (r - l + 1);
if(m > sz / 2){
m = sz - m + 1;
}
ll s1 = sm(1 , 0 , n - 1 , l , l + m - 2 , 1) - l * sm(1 , 0 , n - 1 , l , l + m - 2 , 0);
ll s2 = sm(1 , 0 , n - 1 , l + m - 1 , r - m + 1 , 0) * m;
ll s3 = sm(1 , 0 , n - 1 , r - m + 2 , r , 2) - (( n - ( r - ( m - 2 ))) - ( m - 1 )) * sm(1 , 0 , n - 1 , r - m + 2 , r , 0);
cout << s1 + s2 + s3 << endl;
}
}
}
/*
if(r - l + 1 <= (m - 1) * 2){
ll x = l + (r - l + 1) / 2 - 1, y = x + 1;
//cout << "X: " << x - l << " " << "Y: " << y - l << endl;
ll s1 = sm(1 , 0 , n - 1 , l , x , 1) - sm(1 , 0 , n - 1 ,l , x , 0) * l;
ll s2 = sm(1 , 0 , n - 1 , y , r , 2) - sm(1 , 0 , n - 1 , y , r , 0) * (n - r - 1);
//cout << s1 << endl;
//cout << s2 << endl;
//cout << "ESAA PAS: ";
cout << s1 + s2 << endl;
}else{
ll x = l + m - 2, y = r - m + 2;
//cout << "X: " << x << " " << "Y: " << y << endl;
ll s1 = sm(1 , 0 , n - 1 , x + 1 , y - 1 , 0) * m;
ll s2 = 0 , s3 = 0;
if(x >= l) s2 = sm(1 , 0 , n - 1 , l , x , 1) - sm(1 , 0 , n - 1 , l , x , 0) * l;
if(y <= r) s3 = sm(1 , 0 , n - 1 , y , r , 2) - sm(1 , 0 , n - 1 , y , r , 0) * (n - r - 1);
cout << s1 + s2 + s3 << endl;
}
8 3
7 2 5 1 9 3 4 6
1
1 2 5 8
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
Output is correct |
| 2 |
Correct |
3 ms |
340 KB |
Output is correct |
| 3 |
Correct |
5 ms |
468 KB |
Output is correct |
| 4 |
Correct |
10 ms |
596 KB |
Output is correct |
| 5 |
Correct |
14 ms |
596 KB |
Output is correct |
| 6 |
Correct |
18 ms |
904 KB |
Output is correct |
| 7 |
Correct |
17 ms |
988 KB |
Output is correct |
| 8 |
Correct |
18 ms |
980 KB |
Output is correct |
| 9 |
Correct |
25 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
2700 KB |
Output is correct |
| 2 |
Correct |
78 ms |
3320 KB |
Output is correct |
| 3 |
Correct |
126 ms |
5224 KB |
Output is correct |
| 4 |
Correct |
201 ms |
9804 KB |
Output is correct |
| 5 |
Correct |
288 ms |
11236 KB |
Output is correct |
| 6 |
Correct |
278 ms |
10952 KB |
Output is correct |
| 7 |
Correct |
259 ms |
10920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
6284 KB |
Output is correct |
| 2 |
Correct |
267 ms |
10544 KB |
Output is correct |
| 3 |
Correct |
326 ms |
12472 KB |
Output is correct |
| 4 |
Correct |
401 ms |
11464 KB |
Output is correct |
