oj.uz

Submission #774780

# Submission time Handle Problem Language Result Execution time Memory
774780 2023-07-06T03:14:56 Z vjudge1 Addk (eJOI21_addk) C++
100 / 100
 210 ms 8756 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Node
{
    int tang, sum, giam;
};
Node st[400005];
int a[100001], n, k;
Node combine(Node a, Node b)
{
    Node ans;
    ans.tang = a.tang + b.tang;
    ans.sum = a.sum + b.sum;
    ans.giam = a.giam + b.giam;
    return ans;
}
void build(int node, int l, int r)
{
    if(l == r){
        st[node].sum = a[l];
        st[node].tang = a[l]*l;
        st[node].giam = a[l]*(n-l+1);
    }
    else{
        build(node*2, l, (l+r)/2);
        build(node*2+1, (l+r)/2+1, r);
        st[node] = combine(st[node*2], st[node*2+1]);
    }
}
void update(int node, int l, int r, int p, int v)
{
    if(r < p || l > p) return;
    if(l == p && r == p){
        a[p] = v;
        st[node].sum = a[l];
        st[node].tang = a[l]*l;
        st[node].giam = a[l]*(n-l+1);
    }
    else{
        update(node*2, l, (l+r)/2, p, v);
        update(node*2+1, (l+r)/2+1, r, p, v);
        st[node] = combine(st[node*2], st[node*2+1]);
    }
}
int query(int node, int l, int r, int tl, int tr)
{
    if(l > tr || r < tl) return 0;
    else if(l >= tl && r <= tr) return st[node].sum;
    else return query(node*2, l, (l+r)/2, tl, tr) + query(node*2+1, (l+r)/2+1, r, tl, tr);
}
int queryTang(int node, int l, int r, int tl, int tr)
{
    if(l > tr || r < tl) return 0;
    else if(l >= tl && r <= tr) return st[node].tang;
    else return queryTang(node*2, l, (l+r)/2, tl, tr) + queryTang(node*2+1, (l+r)/2+1, r, tl, tr);
}
int queryGiam(int node, int l, int r, int tl, int tr)
{
    if(l > tr || r < tl) return 0;
    else if(l >= tl && r <= tr) return st[node].giam;
    else return queryGiam(node*2, l, (l+r)/2, tl, tr) + queryGiam(node*2+1, (l+r)/2+1, r, tl, tr);
}
int tiento(int l, int r)
{
    if(r < l) return 0;
    else return queryTang(1, 1, n, l, r) - (l-1) * query(1, 1, n, l, r);
}
int hauto(int l, int r)
{
    if(r < l) return 0;
    else return queryGiam(1, 1, n, l, r) - (n-r) * query(1, 1, n, l, r);
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build(1, 1, n);
    int q;
    cin>>q;
    for(int test = 0; test < q; test++){
        int type;
        cin>>type;
        if(type == 1){
            vector<int> wtf(k);
            for(int i = 0; i < k; i++) cin>>wtf[i];
            int re = a[wtf[0]];
            for(int i = 0; i < k; i++) update(1, 1, n, wtf[i], a[wtf[i+1]]);
            update(1, 1, n, wtf[k-1], re);
            //cout<<a[wtf[0]]<<" "<<a[wtf[1]]<<" "<<a[wtf[2]]<<" "<<wtf[0]<<" "<<wtf[1]<<" "<<wtf[2]<<endl;
        }
        else{
            int l, r, m;
            cin>>l>>r>>m;
            int maximum;
            if(r-l+1 >= 2*m-1) maximum = m;
            else maximum = m-(2*m-1 - (r-l+1));
            //cout<<maximum<<'\n';
            int x = tiento(l, l+maximum-2), y = hauto(r-maximum+2, r), z = maximum * query(1, 1, n, l+maximum-1, r-maximum+1);
            //cout<<x<<" "<<y<<" "<<z<<endl;
            cout<<x+y+z<<'\n';
        }
    }
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 5 ms 576 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 8 ms 724 KB Output is correct
8 Correct 12 ms 852 KB Output is correct
9 Correct 14 ms 1236 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2256 KB Output is correct
2 Correct 44 ms 2480 KB Output is correct
3 Correct 62 ms 4276 KB Output is correct
4 Correct 112 ms 8028 KB Output is correct
5 Correct 163 ms 8756 KB Output is correct
6 Correct 152 ms 8524 KB Output is correct
7 Correct 152 ms 8524 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 4232 KB Output is correct
2 Correct 144 ms 8164 KB Output is correct
3 Correct 210 ms 8000 KB Output is correct
4 Correct 172 ms 8652 KB Output is correct