oj.uz

Submission #775246

# Submission time Handle Problem Language Result Execution time Memory
775246 2023-07-06T09:00:42 Z burythelightdeepwithin Addk (eJOI21_addk) C++14
100 / 100
 1607 ms 8400 KB 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll maxn=200005;

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

void make_tree(ll pos, ll low, ll high)
{
    if(low==high)
    {
        tree[pos]=a[low];
        return;
    }
    ll 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(ll pos, ll low, ll high, ll query, ll up)
{
    if (query>high || query<low)
    {
        return;
    }
    if (low==high)
    {
        tree[pos]=up;
        return;
    }
    ll 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];
}

ll SumQuery(ll pos, ll low, ll high, ll qlow, ll qhigh)
{
    if (qlow>high || qhigh<low)
    {
        return 0;
    }
    if (qlow<=low && high<=qhigh)
    {
        return tree[pos];
    }
    ll 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 (ll i=0; i<n; i++)
    {
        cin >> a[i];
    }
    make_tree(0,0,n-1);
    cin >> m;
    while (m--)
    {
        ll t;
        cin >> t;
        if (t==1)
        {
            vector<ll>v;
            for (ll j=1; j<=k; j++)
            {
                ll 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 (ll 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;
			ll cnt=0;
			while (ptr1<=ptr2 && ptr2>=l+m-1 && cnt<m)
			{
				sum+=ans;
				ans-=(a[ptr1]+a[ptr2]);
				ptr2--; ptr1++;
				cnt++;
			}
			cout << sum << endl;
        }
    }
}

Compilation message

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<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             for (ll i=1; i<v.size(); i++)
      |                          ~^~~~~~~~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 9 ms 548 KB Output is correct
6 Correct 12 ms 628 KB Output is correct
7 Correct 15 ms 676 KB Output is correct
8 Correct 25 ms 736 KB Output is correct
9 Correct 32 ms 952 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 1364 KB Output is correct
2 Correct 199 ms 2224 KB Output is correct
3 Correct 346 ms 3204 KB Output is correct
4 Correct 1063 ms 5624 KB Output is correct
5 Correct 1607 ms 6752 KB Output is correct
6 Correct 1417 ms 6660 KB Output is correct
7 Correct 1240 ms 6680 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 3700 KB Output is correct
2 Correct 1073 ms 6508 KB Output is correct
3 Correct 258 ms 8400 KB Output is correct
4 Correct 1555 ms 7516 KB Output is correct