oj.uz

답안 #775250

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
775250 2023-07-06T09:02:30 Z burythelightdeepwithin Addk (eJOI21_addk) C++14
100 / 100
 1603 ms 4660 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 tmp=SumQuery(0,0,n-1,l,r);
            ll ptr1=l, ptr2=r;
            ll ans=0;
            ll cnt=0;
            while (ptr1<=ptr2 && ptr2>=l+m-1)
            {
                if (cnt>=m)
                {
                    break;
                }
                else
                {
                    ans+=tmp;
                    tmp-=(a[ptr1]+a[ptr2]);
                    ptr2--; ptr1++;
                    cnt++;
                }
            }
            cout << ans << 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

# 결과 실행 시간 메모리 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 448 KB Output is correct
5 Correct 9 ms 488 KB Output is correct
6 Correct 12 ms 468 KB Output is correct
7 Correct 15 ms 568 KB Output is correct
8 Correct 19 ms 588 KB Output is correct
9 Correct 32 ms 728 KB Output is correct

Subtask #2
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 1228 KB Output is correct
2 Correct 201 ms 1488 KB Output is correct
3 Correct 335 ms 2332 KB Output is correct
4 Correct 1027 ms 3908 KB Output is correct
5 Correct 1603 ms 4660 KB Output is correct
6 Correct 1477 ms 4444 KB Output is correct
7 Correct 1246 ms 4556 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 281 ms 2184 KB Output is correct
2 Correct 1045 ms 4020 KB Output is correct
3 Correct 252 ms 3788 KB Output is correct
4 Correct 1530 ms 4644 KB Output is correct