Submission #1244230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244230		borisAngelov	Simple game (IZhO17_game)	C++20	100 / 100	273 ms	25932 KiB

game

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int MAX = 1000000;

int n, q;
int a[maxn];

struct SegmentTree
{
    long long tree[4 * MAX + 50];
    int lazy[4 * MAX + 50];

    void pushLazy(int node, int l, int r)
    {
        if (lazy[node] == 0) return;
        tree[node] += (1LL * lazy[node]) * (1LL * (r - l + 1));

        if (l != r)
        {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }

        lazy[node] = 0;
    }

    void update(int node, int l, int r, int ql, int qr, int delta)
    {
        pushLazy(node, l, r);
        if (l > qr || r < ql) return;
        
        if (ql <= l && r <= qr)
        {
            lazy[node] += delta;
            pushLazy(node, l, r);
            return;
        }
        
        int mid = (l + r) / 2;
        update(2 * node, l, mid, ql, qr, delta);
        update(2 * node + 1, mid + 1, r, ql, qr, delta);

        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    int queryPoint(int node, int l, int r, int pos)
    {
        pushLazy(node, l, r);
        if (l == r) return tree[node];

        int mid = (l + r) / 2;
        if (pos <= mid) return queryPoint(2 * node, l, mid, pos);
        else return queryPoint(2 * node + 1, mid + 1, r, pos);
    }

    void update(int l, int r, int delta)
    {
        if (l > r) swap(l, r);
        //cout << "add " << l << " " << r << " :: " << delta << endl;
        update(1, 1, MAX, l, r, delta);
    }

    int queryPoint(int pos)
    {
        return queryPoint(1, 1, MAX, pos);
    }
};

SegmentTree tree;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> q;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

    for (int i = 1; i < n; ++i)
    {
        if (a[i] != a[i + 1])
        {
            tree.update(a[i], a[i + 1], +1);
        }
    }

    while (q--)
    {
        int type;
        cin >> type;

        if (type == 1)
        {
            int pos, x;
            cin >> pos >> x;

            if (pos > 1 && a[pos] != a[pos - 1]) tree.update(a[pos], a[pos - 1], -1);
            if (pos < n && a[pos] != a[pos + 1]) tree.update(a[pos], a[pos + 1], -1);
            
            a[pos] = x;

            if (pos > 1 && a[pos] != a[pos - 1]) tree.update(a[pos], a[pos - 1], +1);
            if (pos < n && a[pos] != a[pos + 1]) tree.update(a[pos], a[pos + 1], +1);
        }
        else
        {
            int h;
            cin >> h;
            cout << tree.queryPoint(h) << "\n";
        }
    }

    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51