Submission #775332

#	Time	Username	Problem	Language	Result	Execution time	Memory
775332		vjudge1	Addk (eJOI21_addk)	C++17	64 / 100	363 ms	11548 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const long long MODULO = 998244353;

struct SegmentTree
{
    int n = 0;
    vector<long long> segTreeA, segTreeB, segTreeC;

    void resize(const int& _n)
    {
        n = _n;
        segTreeA.clear(), segTreeA.resize(4 * n);
        segTreeB.clear(), segTreeB.resize(4 * n);
        segTreeC.clear(), segTreeC.resize(4 * n);
    }

    void _pointUpdate(const int& node, const int& left, const int& right, const int& qIndex, const long long& qValue)
    {
        if (left + 1 == right)
        {
            segTreeA[node] = segTreeB[node] = segTreeC[node] = qValue;
            return;
        }

        int mid = (left + right) >> 1;
        if (qIndex < mid)
            _pointUpdate(2 * node + 1, left, mid, qIndex, qValue);
        else
            _pointUpdate(2 * node + 2, mid, right, qIndex, qValue);

        segTreeA[node] = segTreeA[2 * node + 1] + segTreeA[2 * node + 2];
        segTreeB[node] = segTreeB[2 * node + 1] + segTreeB[2 * node + 2] + segTreeA[2 * node + 2] * (mid - left);
        segTreeC[node] = segTreeC[2 * node + 1] + segTreeC[2 * node + 2] + segTreeA[2 * node + 1] * (right - mid);
    }

    void pointUpdate(const int& qIndex, const long long& qValue)
    {
        _pointUpdate(0, 0, n, qIndex, qValue);
    }

    long long _rangeQuery(const int& node, const int& left, const int& right, const int& qLeft, const int& qRight, const char& qType)
    {
        if (qRight <= left || right <= qLeft) return 0;
        if (qLeft <= left && right <= qRight)
        {
            if (qType == 'A') return segTreeA[node];
            if (qType == 'B') return segTreeB[node] + segTreeA[node] * (left - qLeft);
            if (qType == 'C') return segTreeC[node] + segTreeA[node] * (qRight - right);
            return -1;
        }

        int mid = (left + right) >> 1;
        return _rangeQuery(2 * node + 1, left, mid, qLeft, qRight, qType)
            + _rangeQuery(2 * node + 2, mid, right, qLeft, qRight, qType);
    }

    long long rangeQuery(const int& qLeft, const int& qRight, const char& qType)
    {
        return _rangeQuery(0, 0, n, qLeft, qRight, qType);
    }
} segTree;

int n, k, queries;
vector<int> v;
vector<int> prevIndex;
vector<long long> prevValue;

int main()
{
    // std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();

    // freopen("inp.txt", "r", stdin);

    ios::sync_with_stdio(false);

    cin >> n >> k;
    v.resize(n);
    segTree.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        segTree.pointUpdate(i, v[i]);
    }

    prevIndex.resize(k);
    prevValue.resize(k);
    int type, l, r, m;
    cin >> queries;
    while (queries --> 0)
    {
        cin >> type;

        if (type == 1)
        {
            for (int i = 0; i < k; i++)
            {
                cin >> prevIndex[i], prevIndex[i]--;
                prevValue[i] = segTree.rangeQuery(prevIndex[i], prevIndex[i] + 1, 'A');
            }

            for (int i = 1; i < k; i++)
                segTree.pointUpdate(prevIndex[i - 1], prevValue[i]);
            segTree.pointUpdate(prevIndex[k - 1], prevValue[0]);
        }
        else
        {
            cin >> l >> r >> m, l--;

            int length = r - l;
            int lengthBC = min(length - m + 1, m), lengthA = length - 2 * lengthBC;

            long long result = segTree.rangeQuery(l, l + lengthBC, 'B')
                               + segTree.rangeQuery(l + lengthBC, l + lengthBC + lengthA, 'A') * min(length - m + 1, m)
                               + segTree.rangeQuery(l + lengthBC + lengthA, r, 'C');

            cout << result << '\n';
        }
    }

    // std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
    // std::cout << endl << "Time difference = " << std::chrono::duration_cast<std::chrono::milliseconds> (end - begin).count() << "[ms]" << std::endl;
}

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