oj.uz

Submission #641099

# Submission time Handle Problem Language Result Execution time Memory
641099 2022-09-16T01:47:03 Z kith14 Addk (eJOI21_addk) C++17
100 / 100
 511 ms 8728 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>

#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

const ll N = 1e5+5, MOD = 1e9+7;
ll tc = 1, n, m, ar[N], br[N], tree[N*4][3];
ll x, y, k;
string s, s1, s2, ye = "YES", no = "NO";

void build(ll l, ll r, ll idx, ll cr){
  if (l == r){
    if (cr == 0) tree[idx][cr] = ar[l];
    else if (cr == 1) tree[idx][cr] = ar[l]*l;
    else tree[idx][cr] = ar[l]*(n-l+1);
    return;
  }
  ll md = (l+r)/2;
  build(l,md,idx*2,cr);
  build(md+1,r,idx*2+1,cr);
  tree[idx][cr] = tree[idx*2][cr]+tree[idx*2+1][cr];
}

ll que(ll l, ll r, ll idx, ll x, ll y, ll cr){
  if (l > r || l > y || r < x) return 0;
  if (x <= l && r <= y) return tree[idx][cr];
  ll md = (l+r)/2;
  return que(l,md,idx*2,x,y,cr)+que(md+1,r,idx*2+1,x,y,cr); 
}

void upd(ll l, ll r, ll idx, ll pos, ll val, ll cr){
  if (l == r){
    if (cr == 0) tree[idx][cr] = val;
    else if (cr == 1) tree[idx][cr] = val*l;
    else tree[idx][cr] = val*(n-l+1);
    return;
  }
  ll md = (l+r)/2;
  if (pos <= md) upd(l,md,idx*2,pos,val,cr);
  else upd(md+1,r,idx*2+1,pos,val,cr);
  tree[idx][cr] = tree[idx*2][cr]+tree[idx*2+1][cr];
}

void input(){
  cin >> n >> k;
  repp(i,1,n) cin >> ar[i];
}

void solve(){
  build(1,n,1,0);
  build(1,n,1,1);
  build(1,n,1,2);
  cin >> m;
  while(m--){
    ll a, b, c, d;
    cin >> a;
    if (a == 1){
      vector<ll> idx, val;
      ll lst;
      repp(i,1,k){
        cin >> b;
        idx.pb(b);
        if (i != 1) val.pb(ar[b]);
        else lst = ar[b];
      }
      val.pb(lst);
      repz(i,0,k){
        upd (1,n,1,idx[i],val[i],0);
        upd (1,n,1,idx[i],val[i],1);
        upd (1,n,1,idx[i],val[i],2);
        ar[idx[i]] = val[i];
      }
      continue;
    }
    cin >> b >> c >> d;
    ll len = c-b+1;
    if (d > (len+1)/2) d = len-d+1;
    //cout << "d = " << d << endl;
    ll ten = que(1,n,1,b+d,c-d,0)*d;
    ll kir= que(1,n,1,b,b+d-1,1)-que(1,n,1,b,b+d-1,0)*(b-1);
    ll kan = que(1,n,1,c-d+1,c,2)-que(1,n,1,c-d+1,c,0)*(n-c);
    ll tot = kir+kan+ten;
    if (len%2 && d == (len+1)/2){
      tot -= que(1,n,1,b+d-1,b+d-1,0)*d;
    }
    cout << tot << endl;
    //cout << kir << " " << ten << " " << kan << endl;
  }
  // while(m--){
  //   ll a, b, c;
  //   cin >> c;
  //   cout << tree[1][c] << endl;
  // }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  //cin >> tc;
  while(tc--){
    input();
    solve();
  }
}

/*

*/

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 7 ms 604 KB Output is correct
5 Correct 10 ms 676 KB Output is correct
6 Correct 13 ms 852 KB Output is correct
7 Correct 15 ms 924 KB Output is correct
8 Correct 18 ms 976 KB Output is correct
9 Correct 26 ms 1492 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2284 KB Output is correct
2 Correct 80 ms 2520 KB Output is correct
3 Correct 122 ms 4260 KB Output is correct
4 Correct 203 ms 7960 KB Output is correct
5 Correct 302 ms 8656 KB Output is correct
6 Correct 277 ms 8548 KB Output is correct
7 Correct 282 ms 8724 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 4276 KB Output is correct
2 Correct 267 ms 8168 KB Output is correct
3 Correct 511 ms 7948 KB Output is correct
4 Correct 335 ms 8728 KB Output is correct