Submission #775187

#	Time	Username	Problem	Language	Result	Execution time	Memory
775187		vjudge1	Addk (eJOI21_addk)	C++17	0 / 100	2060 ms	242232 KiB

Main

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn=200005;

int n,m,k;
int a[maxn];
int tree[4*maxn];

void make_tree(int pos, int low, int high)
{
    if(low==high)
    {
        tree[pos]=a[low];
        return;
    }
    int mid=(low+high)/2;
    make_tree(2*pos+1,low,mid);
    make_tree(2*pos+2,mid+1,high);
    tree[pos]=(tree[2*pos+1]+tree[2*pos+2]);
}

void update(int pos, int low, int high, int query, int up)
{
    if (query>high || query<low)
    {
        return;
    }
    if (low==high)
    {
        tree[pos]=up;
        return;
    }
    int mid=(low+high)/2;
    update(2*pos+1,low,mid,query,up);
    update(2*pos+2,mid+1,high,query,up);
    tree[pos]=tree[2*pos+1]+tree[2*pos+2];
}

int SumQuery(int pos, int low, int high, int qlow, int qhigh)
{
    if (qlow>high || qhigh<low)
    {
        return 0;
    }
    if (qlow<=low && high<=qhigh)
    {
        return tree[pos];
    }
    int mid=(low+high)/2;
    return SumQuery(2*pos+1,low,mid,qlow,qhigh)+SumQuery(2*pos+2,mid+1,high,qlow,qhigh);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for (int i=0; i<n; i++)
    {
        cin >> a[i];
    }
    make_tree(0,0,n-1);
    cin >> m;
    while (m--)
    {
        int t;
        cin >> t;
        if (t==1)
        {
            vector<int>v;
            for (int j=1; j<=k; j++)
            {
                int x;
                cin >> x;
                x--;
                v.push_back(x);
            }
            ll cur=a[v[0]];
            for (ll i=1; i<v.size(); i++)
            {
                a[v[i-1]]=a[v[i]];
            }
            a[v[v.size()-1]]=cur;
            for (auto it:v)
            {
                update(0,0,n-1,it,a[it]);
            }
            for (int i=0; i<n; i++) {
                cout << a[i] << " ";
            }
            cout << endl;
        } else {
            ll l,r,m;
			cin >> l >> r >> m;
			l--; r--;
			ll ans=SumQuery(0,0,n-1,l,r);
			ll ptr1=l, ptr2=r;
			ll sum=0;
			while (ptr1<=ptr2 && ptr2>=l+m-1)
			{
				sum+=ans;
				ans-=(a[ptr1]+a[ptr2]);
				ptr1++; ptr2--;
			}
			cout << sum << endl;
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:82:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             for (ll i=1; i<v.size(); i++)
      |                          ~^~~~~~~~~

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