Submission #1073261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073261		MrPavlito	Addk (eJOI21_addk)	C++17	0 / 100	79 ms	5956 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 1e6+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;

int niz[MAXN];
int n;
int seg[MAXN<<2];
int prefseg[MAXN<<2];
int sufseg[MAXN<<2];

void build(int nod, int tl, int tr)
{
    if(tl==tr)
    {
        seg[nod] = niz[tl];
        prefseg[nod] = niz[tl]*tl;
        sufseg[nod] = niz[tl]*(n- tl+1);
        return;
    }
    int mid = tl+tr>>1;
    build(nod<<1, tl, mid);
    build(nod<<1|1, mid+1, tr);
    seg[nod] = seg[nod<<1] + seg[nod<<1|1];
    prefseg[nod] = prefseg[nod<<1] + prefseg[nod<<1|1];
    sufseg[nod] = sufseg[nod<<1] + sufseg[nod<<1|1];
}

void update(int nod, int tl, int tr, int index, int v)
{
    if(tl == tr)
    {
        niz[index] = v;
        seg[nod] = niz[tl];
        prefseg[nod] = niz[tl]*tl;
        sufseg[nod] = niz[tl]*(n- tl+1);
        return;
    }
    int mid = tl+tr>>1;
    if(index<= mid)update(nod<<1, tl, mid, index, v);
    else update(nod<<1|1, mid+1, tr, index, v);
    seg[nod] = seg[nod<<1] + seg[nod<<1|1];
    prefseg[nod] = prefseg[nod<<1] + prefseg[nod<<1|1];
    sufseg[nod] = sufseg[nod<<1] + sufseg[nod<<1|1];
}

int querysuf(int nod, int tl, int tr, int l, int r)
{
    if(tl> r || tr< l || tl>tr)return 0;
    if(tl>=l && tr<=r)return sufseg[nod];
    int mid = tl+tr>>1;
    return querysuf(nod<<1, tl, mid, l, r) + querysuf(nod<<1|1, mid+1, tr, l, r);
}


int querypref(int nod, int tl, int tr, int l, int r)
{
    if(tl> r || tr< l || tl>tr)return 0;
    if(tl>=l && tr<=r)return prefseg[nod];
    int mid = tl+tr>>1;
    int q1 = querypref(nod<<1, tl, mid, l, r);
    int q2 = querypref(nod<<1|1, mid+1, tr, l, r);
    return  q1 + q2;
}

int query(int nod, int tl, int tr, int l, int r)
{
    if(tl> r || tr< l || tl>tr)return 0;
    if(tl>=l && tr<=r)return seg[nod];
    int mid = tl+tr>>1;
    return query(nod<<1, tl, mid, l, r) + query(nod<<1|1, mid+1, tr, l, r);
}

signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        int q,k;
        cin >> n >> k;
        for(int i=1; i<=n; i++)cin >> niz[i];
        cin >> q;
        int svi[k];
        build(1,1,n);
        while(q--)
        {
            int t;cin >> t;
            if(t == 1)
            {
                for(int i=0; i<k; i++)cin >> svi[i];
                int prvi = svi[0];
                for(int i=0; i<k-1; i++)update(1,1,n, svi[i], niz[svi[i+1]]);
                update(1,1,n, svi[k-1], prvi);
            }
            else
            {
                int m,l,r;cin >> l >> r >> m;
                if(r-l+1 == m)cout << query(1,1,n,l,r) << endl;
                else if(m <= (r-l+2)/2)
                {
                    int mid = m-1;
                    int p1 = querypref(1,1,n, 1, l+mid-1) - querypref(1,1,n,1, l-1)- query(1,1,n,l,l+mid-1)*(l-1);
                    int p2 = querysuf(1,1,n, r-mid+1, n) - querysuf(1,1,n,r+1, n) - query(1,1,n,r-mid+1,r)*(n-r);
                    int p3 = query(1,1,n,l+mid, r- mid)*m;
                    cout << p1+p2+p3 << endl;
                }
                else
                {
                    int mid = (r-l+2) - m;
                    int p1 = querypref(1,1,n, 1, l+mid-1) - querypref(1,1,n,1, l-1)- query(1,1,n,l,l+mid-1)*(l-1);
                    int p2 = querysuf(1,1,n, r-mid+1, n) - querysuf(1,1,n,r+1, n) - query(1,1,n,r-mid+1,r)*(n-r);
                    int p3 = query(1,1,n,l+mid, r- mid)*mid;
                    cout << p1+p2+p3 << endl;
                }
            }
        }
    }
}

/*
10 1
1 1 1 1 1 1 1 1 1 1
5
2 2 9 6
*/

Compilation message (stderr)

Main.cpp: In function 'void build(long long int, long long int, long long int)':
Main.cpp:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid = tl+tr>>1;
      |               ~~^~~
Main.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = tl+tr>>1;
      |               ~~^~~
Main.cpp: In function 'long long int querysuf(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int mid = tl+tr>>1;
      |               ~~^~~
Main.cpp: In function 'long long int querypref(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int mid = tl+tr>>1;
      |               ~~^~~
Main.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     int mid = tl+tr>>1;
      |               ~~^~~

• Subtask 1: 0 / 36
• Subtask 2: 0 / 56
• Subtask 3: 0 / 8